剑指 Offer II 006. 排序数组中两个数字之和

解题思路

使用HashMap解决问题固然可以,但是常数的时间还是要大于双指针的 因为是排序数组,所以使用 sum = numbers[left]+numbers[right] 进行判断

如果 sum > target , 那么 right-- 如果 sum < target , 那么 left++

代码

class Solution {
          
   
    public int[] twoSumA(int[] numbers, int target) {
          
   
        // 使用HashMap进行解题
        HashMap<Integer,Integer> map = new HashMap<>();
        for(int i=0; i<numbers.length; i++){
          
   
            if(map.containsKey(target-numbers[i])) return new int[] {
          
   map.get(target-numbers[i]),i};
            map.put(numbers[i],i);
        }
        return new int[] {
          
   0,0};
    }
    // 使用双指针来解决问题
    public int[] twoSum(int[] numbers, int target) {
          
   
        int left=0, right=numbers.length-1;
        while(left<right){
          
   
            int sum = numbers[left] + numbers[right]; // 可以不使用变量来记录
            if(sum==target) return new int[] {
          
   left,right};
            else if(sum>target) right--;
            else left++;
        }
        return new int[] {
          
   0,0};
    }
}