leetcode two sum

two sum

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

twosum

• 方案一使用哈希表

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap();
        for(int i = 0; i<nums.length; i++){
            map.put(nums[i], i);
        }
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            if (map.containsKey(complement) && map.get(complement) != i) {
                return new int[] { i, map.get(complement) };
            }
        }
        return null;
    }
}

• 方案二快排

class Solution {
    public int[] twoSum(int[] nums, int target) {

		// corner cases
		if (nums == null || nums.length <= 1) {
			return null;
		}
		int[] nums2 = Arrays.copyOf(nums, nums.length);
		Arrays.sort(nums);
		int left = 0;
		int right = nums.length - 1;
		int a = 0;
		int b = 0;
		while (left < right) {
			long sum = (long) nums[left] + (long) nums[right];
			if (sum == target) {
				a = nums[left];
				b = nums[right];
				break;
			} else if (sum < target) {
				left += 1;
			} else {
				right -= 1;
			}
		}
		// find index 1
		for(int i = 0; i < nums2.length; i++){
			if(nums2[i] == a) {
				left = i;
				break;
			}
		}
		// find index 2
		for(int i = nums2.length - 1; i >= 0; i--){
			if(nums2[i] == b) {
				right = i;
				break;
			}
		}
		return new int[]{Math.min(left, right),Math.max(left, right)};


    }
}