leetcode 15.三数之和
给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。 注意：答案中不可以包含重复的三元组。
例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，满足要求的三元组集合为：[[-1, 0, 1],[-1, -1, 2]]
解题思路：
1.先对列表进行排序，方便判断重复的数字。
2.选定nums[i]作为第一个数，则另外两个数之合sum = 0 - nums[i]。
3.nums[i]若大于0，则停止操作。因为列表已经排序，nums[i]后面的数字都是正数，正数之合大于0。
class Solution(object):def threeSum(self, nums):""":type nums: List[int]:rtype: List[List[int]]"""nums_len = len(nums)ls = []if nums_len < 3:return lsnums.sort()for i in range(nums_len - 2):if nums[i] > 0:breakif i == 0 or nums[i] != nums[i - 1]:l = i + 1r = nums_len - 1sum = 0 - nums[i]while l < r:if nums[l] + nums[r] == sum:ls.append((nums[i], nums[l], nums[r]))while l < r and nums[l] == nums[l + 1]:l += 1while l < r and nums[r] == nums[r - 1]:r -= 1l += 1r -= 1elif nums[l] + nums[r] < sum:l += 1else:r -= 1return ls
167.两数之和(有序)
给定一个已按照升序排列 的有序数组，找到两个数使得它们相加之和等于目标数。
函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2。
输入: numbers = [2, 7, 11, 15], target = 9
输出: [1,2]
解释: 2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。
思路：
最直接的思考：暴力解法。双层遍历，O(n^2)
暴力解法没有充分利用原数组的性质 - 有序
有序？二分搜索？O(nlogn)
class Solution:def twoSum(self, numbers: List[int], target: int) -> List[int]:#时间复制读O(n)#空间复杂度O(1)i, j = 0, len(numbers)-1while i < j:if numbers[i] + numbers[j] == target:breakelif numbers[i] + numbers[j] < target:i += 1else:j -= 1return [i+1, j+1]
leetcode1. 两数之和(值不重复)
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
示例：
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
思路：由于是不重复的值，考虑使用字典。字典的key存储值，value存储值的下标。遍历列表，如果target-key不在字典里面，那么把当前的key放入字典。否则返回target-key对应的value和当前值对应的下标。
class Solution:def twoSum(self, nums: List[int], target: int) -> List[int]:dic = {}for i, j in enumerate(nums):if target - j in dic:return [dic[target - j], i]else:dic[j] = i
