LeetCode-T167-两数之和 II - 输入有序数组(two-sum-ii-input-array-is-sorted)

题目

原题链接

题目描述：

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

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

说明:

• 返回的下标值（index1 和 index2）不是从零开始的。
• 你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。

样例

case1：

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

题解

思路

使用Map记录每个元素和下标(item, index)
遍历数组，当Map里面存在 target - numbers[i] 并且 下标不等于i时 ans[0] = i+1 ans[1] = map[target - numbers[i]]

代码

import java.util.HashMap;
import java.util.Map;

/**
 * https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted/
 * 思路：使用Map记录每个元素和下标(item, index)
 *      遍历数组，当Map里面存在 target - numbers[i] 并且 下标不等于i时 ans[0] = i+1 ans[1] = map[target - numbers[i]]
 *
 * @author yingxiang
 */
public class LeetCode_167 {

  public int[] twoSum(int[] numbers, int target) {
    Map<Integer,Integer> index = new HashMap<>(numbers.length + 1);
    for(int i = 0 ; i < numbers.length; i++) {
      index.put(numbers[i], i + 1);
    }
    int[] ans = new int[2];
    for(int i = 0; i < numbers.length; i++) {
      if(index.containsKey(target - numbers[i]) && index.get(target - numbers[i]) != i+1) {
        ans[0] = i + 1;
        ans[1] = index.get(target - numbers[i]);
        break;
      }
    }
    return ans;
  }

  public static void main(String[] args) {
    int[] numbers = new int[]{2,7,11,15};
    int target = 9;
    int[] ans = new LeetCode_167().twoSum(numbers,target);
    System.out.println(ans[0] + " " +ans[1]);
  }
}