1. 两数之和

方法1：利用字典去重

利用字典保存遍历过程变量，若满足条件，则返回结果

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        dic=dict()
        for i,j in enumerate(nums):
            if target-j in dic:
                return [i, dic[target-j]]
            dic[j]=i

class Solution {
public:
    map<int, int>m;
    vector<int>result;
    vector<int> twoSum(vector<int>& nums, int target) {
        int sz=nums.size();
        for (int i = 0; i < sz; ++i) {
            if (m.count(target-nums[i])){
                result.push_back(i);
                result.push_back(m[target-nums[i]]);
            }
            m.insert(make_pair(nums[i],i)); // 或者 m[nums[i]]=i;
        }
    return result;
    }
};

方法2：排序后双指针逼近

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        import copy
        nums1=copy.copy(nums)
        nums1.sort()
        res = []
        l = 0
        r = len(nums1) - 1
        while l < r:
            cur = nums1[l] + nums1[r]
            if cur < target:
                l += 1
            elif cur > target:
                r -= 1
            else:
                break

        # 找到原来的索引
        for i in range(len(nums)):
            if nums[i] in [nums1[l],nums1[r]]:
                res.append(i)
        return res

15. 三数之和

方法1：利用字典去重

在 2Sum 的基础上(如[-10,4,4,5,5,6],对-10 而言，res=[[4,6],[5,5]])，逐个遍历nums ,求满足target为-nums[i] 的结果
对每次的i而言，从i的后面数组中找twoSum(nums[i+1:],target)即可（如[-10,0,1,10,2],与-10相对应的结果为[-10,0,10]。然后遍历0，只要从0的后面（nums[i+1:]）找另外两个数即可,不用管0前面的内容，因为前面能对应到的结果已经找全了）

class Solution(object):
    def threeSum(self, nums):
        def twoSum(nums, target):
            res=[]
            dic = dict()
            for i, j in enumerate(nums):
                if target - j in dic:
                    res.append([j, target - j])
                dic[j] = i
            # 去重，如[[1,2],[1,2],[0,3]] -> [[1,2],[0,3]] (假设target为3)
            resAll=[]
            [resAll.append(i) for i in res if i not in resAll]
            return resAll

        all = []
        nums=sorted(nums)
        for i in range(len(nums)):
            if i>0 and nums[i]==nums[i-1]:continue  # 若有相等元素，则跳过
            target=-nums[i]
            cur=twoSum(nums[i+1:],target)
            # 若没有满足条件的twoSum，对结果也没影响.
            for c in cur: # 对cur中的每组列表都添加当前的nums[i]
                c.append(nums[i])
                all.append(c)
        return all

c++对应的去重方式：如[[1,2],[1,2],[0,3]] -> [[1,2],[0,3]] (假设target为3)
vector<vector<int>> v{{1,2},{1,2},{0,3}};
set<vector<int>> s(v.begin(),v.end());
v.assign(s.begin(),s.end());

方法2：排序后双指针逼近

sorted(nums)先对列表进行排序, 然后用双指针逼近
利用twoSum函数返回满足条件的所有列表
- 如[-10,4,4,5,5,6],对-10 而言，res=[[4,6],[5,5]]
- 设置left，保证nums[l]可以与其左边的元素比较是否相等（right同理）
- for i in range(len(nums)) 对每一次遍历，就是求满足target 为-nums[i] 的结果

class Solution(object):
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        def twoSum(nums, target):
            res = []
            l, r = 0, len(nums) - 1
            while l < r:
                cur = nums[l] + nums[r]
                left = nums[l]
                right = nums[r]
                if cur < target:
                    while l < r and nums[l] == left: l += 1
                elif cur > target:
                    while l < r and nums[r] == right: r -= 1
                else:
                    res.append([nums[l], nums[r]])
                    # 设置left，保证nums[l]可以与其左边的元素比较是否相等（right 同理）
                    while l < r and nums[l] == left: l += 1# 一直向右跳，直到不相等
                    while l < r and nums[r] == right: r -= 1
            print(res)
            return res

        all = []
        nums=sorted(nums)
        for i in range(len(nums)):
            if i>0 and nums[i]==nums[i-1]:continue  # 若有相等元素，则跳过
            target=-nums[i]
            cur=twoSum(nums[i+1:],target)
            # 若没有满足条件的twoSum，则 不执行下面语句.因为cur为[].
            for c in cur:
                c.append(nums[i])
                all.append(c)
        return all

nSum的变体

nums中可能有多对元素之和都等于 target，请返回所有和为 target 的元素对，且不能出现重复。

比如输入为 nums = [1,3,1,2,2,3], target = 4，那么算法返回的结果就是：[[1,3],[2,2]]

排序
通过左右指针更新，若有相同元素，则跳过。left = nums[l]和right = nums[r] 的作用是记录当前位置，从而便于后续跳过相同的元素

def twoSum(nums, target):
    l = 0
    r = len(nums) - 1
    nums = sorted(nums)
    res = []
    while l < r:
        sum = nums[l] + nums[r]
        left = nums[l]
        right = nums[r]# 便于后续跳过相同的元素
        if sum < target:
            l += 1
        elif sum > target:
            r -= 1
        else:
            res.append([nums[l], nums[r]])
            while l < r and nums[l] == left: l += 1
            while l < r and nums[r] == right: r -= 1
    print(res)
nums = [1, 3, 1, 2, 2, 3]
target = 4
twoSum(nums,target)
# 结果为：[[1, 3], [2, 2]]