两数之和 - 双指针、字典

1. 两数之和

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

暴力遍历

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        n = len(nums)
        for x in range(n):
            y = target - nums[x]
            if y in nums:
                if nums.count(y) == 1 and y == nums[x]:
                    continue
                else:
                    y_index = nums.index(y,x+1)
                    # 输入只会对应一个答案
                    break
        # 有可能找不到
        if y_index:
            return [x,y_index]
        else:
            return []

优化暴力

先找到一个x，再从 x 之前的部分查找 y

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        n = len(nums)
        for x in range(1,n):
            temp = nums[:x]
            if (target - nums[x]) in temp:
                y_index = temp.index(target - nums[x])
                break
        if y_index:
            return [y_index,x]
        else:
            return []

先找x，再从 x 之后的部分查找 y
注意： y_index 一开始只有在 x 之后的部分 的，需要加上 x_index + 1

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        n = len(nums)
        for x in range(0,n-1):
            temp = nums[x+1:]
            if (target - nums[x]) in temp:
                y_index = temp.index(target - nums[x]) + x + 1
                break
        if y_index:
            return [x,y_index]
        else:
            return []

字典模拟哈希

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hashmap={}
        for num_index,num in enumerate(nums):
            hashmap[num] = num_index
        for num_index,num in enumerate(nums):
            x = None
            if (target - num) in hashmap:
                x = hashmap[target - num]
            if x and num_index!=x:
                return [num_index,x]

优化哈希 建表同时查找

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

167. 两数之和 II - 输入有序数组

给定一个已按照升序排列 的有序数组，找到两个数使得它们相加之和等于目标数。
函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2。
说明:
返回的下标值（index1 和 index2）不是从零开始的。
你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。

示例:
输入: numbers = [2, 7, 11, 15], target = 9
输出: [1,2]
解释: 2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。

双指针

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        n = len(numbers)
        if n < 2:
            return []
        L,R = 0,n-1
        while L < R :
            if target == numbers[L] + numbers[R]:
                return[L+1,R+1]
            elif target > numbers[L] + numbers[R]:
                L += 1
            else:
                R -= 1
        return []

字典

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        dic = {}
        for x,x_val in enumerate(numbers):
            y = target - x_val
            if y in dic:
                return([dic[y]+1,x+1])
            dic[x_val] = x
        return []

560. 和为K的子数组

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        num_times = collections.defaultdict(int)
        num_times[0] = 1
        cur_sum = 0
        res = 0
        for i in range(len(nums)):
            cur_sum += nums[i]
            if cur_sum - k in num_times:
                res += num_times[cur_sum - k]
            num_times[cur_sum] += 1
        return res