[每日一题]15. three-sum(字典)

1.这是一道找三个数等于某一值的题目。

链接：
https://leetcode.com/problems/3sum/

这题的做法有两种：

第一种：暴力求法，三层循环，找到相加为target value的值
O(n) = n^3 肯定超时。

第二种：
1.对list进行排序，得到新的list (new_list)
2.做一次循环，计算出 新的target值，new_target = target - list[i]
3.根据new_target 从new_list 中找两个数。因为new_list是排序的所以，left从最小（左）开始，right从最大（右）开始。

• 计算sum = new_list[left] + new_list[right] ?= new_target
• 如果sum< new_target: left 向右移动（即把sum调大一点）
• 如果sum>new_target: right 向左移动（即把sum调小一点）
  O(n) = n^2 做了两次循环。

标注1：这题最恶心的地方是不能有重复的list返回。所以就要进行些判重处理，代码中标记出来了。
标注2：还有人说可以采用字典的方法，但是我觉得，字典需要处理key多值的问题，也不好处理。

2.题解：

class Solution(object):
    def threeSum(self, nums):
        if len(nums) < 3:
            return None
        # 1.排序
        nums.sort()
        # print(nums)
        len_nums = len(nums)
        L = []
        for i in range(len_nums-2):
            # 如果和之前的那个数一样，就往后更新一次。（判重）
            if nums[i] == nums[i-1]:
                continue
            # 更新目标和左右指针
            target = -nums[i]
            left = i+1
            right = len_nums-1
            while left < right:
                sum = nums[left] + nums[right]
                if sum < target:
                    left += 1
                elif sum > target:
                    right -= 1
                else:
                    L.append([nums[i], nums[left], nums[right]])
                    # 如果和之前的那个数一样，就往后更新一次。（判重）
                    while left <right and nums[left] == nums[left+1]:
                        left += 1
                    while left < right and nums[right] == nums[right - 1]:
                        right -= 1

                    left += 1
                    right -= 1
        return L

3.完整代码

查看链接：
https://github.com/Wind0ranger/LeetcodeLearn/blob/master/4-dict/15-3sum.py