查找满足两数之和为指定值的元素下标

问题

https://leetcode-cn.com/problems/two-sum/

给定一个整数数组 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]:
        length=len(nums)
        if length<2:
            return
        for i in range(length-1):
            for j in range(i+1,length):
                if nums[i]+nums[j]==target:
                    return i,j

时间复杂度为 \(O(n^2)\)

使用字典

上面的时间复杂度比较高，问题是查找搭配的第二个数又遍历了一次。可以把这一步用字典实现。

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        if len(nums)<2:
            return
        # 字典，key为元素值，value为元素下标
        tmp={}
        for idx,item in enumerate(nums):
            if target-item in tmp:
                return tmp.get(target-item),idx
            # 被遍历的找不到另一半儿的话，把自己存起来，让别的元素来找他
            tmp[item]=idx

时间复杂度为 \(O(n)\)

扩展

下面把问题扩展为查找3个数的下标。

简化为查找2个数

public static List<List<Integer>> threeSumv2(int[] nums, int target) {
        Arrays.sort(nums);
        List<List<Integer>> resultList = new ArrayList<List<Integer>>();
        //大循环
        for (int i = 0; i < nums.length; i++) {
            int d = target - nums[i];
            // j和k双指针循环定位，j在左端，k在右端
            for (int j=i+1,k=nums.length-1; j<nums.length; j++) {
                // k指针向左移动
                while (j<k && (nums[j]+nums[k])>d) {
                    k--;
                }
                //双指针重合，跳出本次循环
                if (j == k) {
                    break;
                }
                if (nums[j] + nums[k] == d) {
                    List<Integer> list = Arrays.asList(nums[i], nums[j], nums[k]);
                    resultList.add(list);
                }
            }
        }
        return resultList;
    }

有序夹逼

对于 有序 数组，可以使用夹逼法，通常用到双指针法，左右两指针向中间移动，直到找到合适的目标。

def three_sum(nums: list, target: int):
    if len(nums) < 3:
       # 长度都不够，return 掉
        return
    # 升序排序
    nums.sort()
    result = []
    for idx, item in enumerate(nums):
        if target < item:
           # 目标值都比遍历到的值小，跳过
            continue
        # 查找和为 target-num 的两个数
        other_2 = target - item
        # 左右夹逼查找
        left = idx + 1
        right = len(nums) - 1
        while left < right:
            if nums[left] + nums[right] < other_2:
                # 小了，往大的尝试
                left += 1
            elif nums[left] + nums[right] > other_2:
               # 大了，往小的尝试
                right -= 1
            else:
                # 正好，记录下来，继续夹逼查
                result.append((idx, left, right))
                left += 1
    return result

时间复杂度：\(O(n^2)\)

空间复杂度：\(O(1)\)