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

问题

给定一个已按照升序排列 的有序数组，找到两个数使得它们相加之和等于目标数。

函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2

例子

思路

• 方法1

  map O(n) O(n)

• 方法2

  双指针 O(n) O(1)

代码

//方法1
class Solution {
    public int[] twoSum(int[] nums, int t) {
        Map<Integer,Integer> map = new HashMap<>();
        for(int i=0; i<nums.length; i++) {
            // 下标值（index1 和 index2）不是从零开始的
            if(map.containsKey(nums[i])) return new int[]{map.get(nums[i])+1,i+1};
            map.put(t-nums[i],i);
        }
        
        return null;
        
    }
}
//方法2
int i=0,j=nums.length-1;
while(i<j) {
    if(nums[i]+nums[j]>t) j--;
    else{
        if(nums[i]+nums[j]<t) i++;
        else return new int[]{i+1,j+1};
    }
        
        
}
return null;