Sort and Hash with unique solution

We analyze how to solve the two sum problem with assumption that there is only one unique solution:

• Using sort and head/tail pointers with O($$NlogN$$) time complexity.
• Using hash table with O($$N$$) time complexity.
• Using brute force method with O($$N^2$$).

Unique solution means that we don't need to consider the duplicates and multiple solution. We just return when we find out a solution.

Leetcode 1. Two Sum

Description:

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.

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

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

Thinking:

Sort + Two Pointer:

public class Solution {
    public int[] twoSum(int[] nums, int target) {
        if(nums == null || nums.length == 0) return null;
        int[] nums2 = Arrays.copyOf(nums, nums.length);
        int[] result = {-1,-1};
        Arrays.sort(nums);
        int a = 0, b = 0;
        int head = 0, tail = nums.length-1;
        while(head < tail){
            if(nums[head]+nums[tail] == target){
                a = nums[head];
                b = nums[tail];
                break;
            }
            else if(nums[head]+nums[tail] < target){
                head++;
            }
            else{
                tail--;
            }
        }
       //Find the index by nums2
       ... ...
       return result; 
    }
}

Hash + Lookup:

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

Brute force method: A nested for loop like the following could easily solve the problem, where for each pair(i,j), we check if nums[i] + nums[j] == target

public class Solution {
    public int[] twoSum(int[] nums, int target) {
        if(nums == null || nums.length == 0) return null;
        int[] result = {-1,-1};
        for(int i = 0; i < nums.length; i++){
          for(int j = i+1; j < nums.length; j++){
            if(nums[i] + nums[j] == target){
              ... ...
              break;
            }
          }
        }
        ... ...
        return result;

Conclusion:

This part gives analysis of the sort and hash method for the classic two sum problem with the assumption that there is only one unique solution and we don't need to consider duplicates and other solutions. However, this is the basic solution which could be regards as preparation for the further deeper analysis of the same two sum problem but without then unique solution assumption where things could be messy and complicated.