[lettcode top 100] 0917 两数之和,有效的括号

1. 两数之和

1. 两数之和 - 力扣（LeetCode）

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标。

思路：

暴力解法，双层循环

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        n = len(nums)
        for i in range(n):
            for j in range(i+1,n):
                if nums[i] +nums[j] == target:
                    return [i,j]

优化：

使用哈希表，可以降低查询target-num时候的复杂度：O(n)->O(1)。（具体为什么能降低，这是哈希表的知识）。将num逐步放入哈希表中，之后target-num在哈希表中寻找。(c++ and python)

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        # 哈希表
        hashtable = {}
        for i,num in enumerate(nums):
            if target - num in hashtable:
                return [i,hashtable[target-num]]
            hashtable[num] = i
        return []

class Solution {
public:
    vector twoSum(vector& nums, int target) {
        //使用map；存储{index,value};
        int n = nums.size();
        unordered_map hastable;
        for (int i = 0;i < n;i++){
            if (hastable.find(target-nums[i]) != hastable.end()){
                return {i,hastable[target-nums[i]]};
            }
            hastable[nums[i]] = i;
        }
        return {};

    }
};

python中的哈希表：dict；collections.OrderedDict()

cpp中的哈希表：unordered_map；unordered_set;

20 有效的括号

20. 有效的括号

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。
3. 每个右括号都有一个对应的相同类型的左括号。

思路：

使用栈来处理括号顺序（有效括号的问题）；维护一个栈，将‘（’，‘[’,‘{’压入到栈中，使用字典，通过 ')'：'(', '}'：'{',']'：'['   dict[key]与栈中元素匹配。(c++ and python)

class Solution {
public:
    bool isValid(string s) {
       //使用栈
       int n = s.length();
       if (n % 2) return false;
       unordered_map mp = {
          {')','('},
          {'}','{'},
          {']','['}
       };
       stack stk;
       for (char& ch:s){
           if (mp.count(ch)){
               if (stk.empty() || mp[ch] != stk.top()){
                   return false;
               }
               stk.pop();
           }
           else stk.push(ch);
       }
       return stk.empty();
    }
};

class Solution:
    def isValid(self, s: str) -> bool:
        n = len(s)
        if (n % 2): return False
        stack = []
        pairs = {
            ')':'(',
            ']':'[',
            '}':'{'
        }
        for ch in s:
            if ch in pairs:
                if not stack or pairs[ch] != stack[-1]:
                    return False 
                stack.pop()
            else:stack.append(ch)
        return not stack