Two Sum leetcode

Given an array of integers, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution.

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

遍历数组

用hashmap 把[num[i](key), i(value)]存入hashmap

如果map中包含target - num[i] 则可以返回num[i] 和target- num[i]的index

没有的话就继续往map中添加

因为只便利一次时间为O(n), 空间为O(n)

public class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] res = new int[2];
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(target - nums[i])) {
                res[0] = map.get(target - nums[i]);
                res[1] = i + 1;
                break;
            } else {
                map.put(nums[i], i + 1);
            }
        }
        return res;
    }
}

如果列表是有序的话 可以用二分法 一个指向最左边 一个指向最右边 如果sum>target right-- else left++
找数据的复杂度是O(n) 排序一般为O(nlogn)

public class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] res = new int[2];
        if (nums.length < 2 || nums == null) {
            return res;
        }
        Arrays.sort(nums);
        int left = 0;
        int right = nums.length - 1;
        while (left < right){
            int sum = nums[left] + nums[right];
            if (sum > target) {
                right--;
            } else if (sum < target) {
                left++;
            } else {
                res[0] = left + 1;
                res[1] = right +1;
                return res;
            }
        }
        return null;
    }
}