题目描述

输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。

示例：

输入：target = 9
输出：[[2,3,4],[4,5]]

思路

1.这道题可以使用“双指针”的思想解决。
2.设置两个指针，分别指向首位两个元素。

  • 当nums[low]+nums[high]==target时，返回双指针对应的数字
  • 当 nums [ low] > target - nums [ high] 时，说明右边的值过大，high- 1
  • 当 nums [ low] < target - nums [ high] 时，说明左边的值过小，low+ 1

Java代码实现

public class Solution {
    public int[] twoSum(int[] nums, int target) {
        int low = 0;
        int high = nums.length-1;

        while(low < high){
            int cur = nums[low]+nums[high];
            if(cur == target){
                return new int[]{nums[low],nums[high]};
            }else if(cur > target){
                high--;
            }else{
                low++;
            }
        }
        return new int[]{-1,-1};
    }
}

Golang代码实现

func twoSum(nums []int, target int) []int {
    low,high := 0,len(nums)-1

    for low < high {
        curSum := nums[low] + nums[high]

        if curSum == target {
            return []int{nums[low],nums[high]}
        }else if curSum > target{
            high--
        }else {
            low++
        }
    }

    return []int{-1,-1}
}