[Algo Rhythm🕺💃] LeetCode 1. Two Sum

📚 Problem 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, 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].

 

🎯 Solution

1. Brute Force

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] ans = new int[2];
        
        for(int i = 0; i < nums.length; i++) {
            boolean flag = false;
            
            for(int j = 0; j < nums.length; j++) {
                if(i == j) continue;
                
                if(nums[i] + nums[j] == target) {
                    ans[0] = i;
                    ans[1] = j;
                    flag = true;
                    break;
                }
            }
            
            if(flag) break;
        }
        
        return ans;
    }
}

2. Hash Map

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

 

🧐 Approach

1. Brute Force

Just pick up an element and find the other element which is same as target when they add. So intuitive and naive. Of course, time complexity is O(n^2).

 

2. Hash Map

Suppose that there are integer 'a' and 'b' that equals to 'target' when they add. In this situation, we know that 'b' is same as 'target - a'.

With this idea and hash, the rest is simple. Just iterate over an array and check whether the difference between target and element is in hash or not. If not, put difference as a key and index as  a value in hash. If has, put indexes of two elements into answer array and return it.

 

📖  What I learned

Hash is powerful thing! 🚀🚀🚀