[数据结构与算法]NC61 两数之和

描述

给出一个整型数组 numbers 和一个目标值 target，请在数组中找出两个加起来等于目标值的数的下标，返回的下标按升序排列。
（注：返回的数组下标从1开始算起）

要求：空间复杂度 O(n)O(n)，时间复杂度 O(nlogn)O(nlogn)

解题

使用HashMap

• 题目要求的是O(nlogn)，那么显然遍历两次的方法是不行的，因此这里使用到了哈希表的方法
• 注意！不用存和找分开两次for进行！
• 可以一遍for就可以，查找，存在则返回，不存在则存储
• 注意值作为key存储，下标当做value
• 这样也不用考虑数组重复的问题，因为先查找，如果有的话都不用存直接返回一个数组就不会存在重复的值的问题！

public class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] arr = new int[]{3, 2, 4};
        int[] ints = solution.twoSum(arr, 6);
        for (int i : ints) {
            System.out.print(i + " ");
        }
    }

    public int[] twoSum(int[] arr, int target) {
         // <value,index>
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < arr.length; i++) {
            if (map.containsKey(target - arr[i])) {
                return new int[]{map.get(target - arr[i]) + 1, i + 1};
            } else {
                map.put(arr[i], i);
            }
        }
        return new int[0];
    }
}