two-sum

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

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

You can return the answer in any order.

Example 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].
Example 2:

Input: nums = [3,2,4], target = 6
Output: [1,2]
Example 3:

Input: nums = [3,3], target = 6
Output: [0,1]

Thinking::
The problem saying that we require to find those two index, if we sum those two, it will match to the target.

Solution #1:
First approach we can do is, do bruiteforce, so that we can point one and then find another one which will led to the solution.

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

        for(int i = 0; i < nums.length; i++) {
            for(int j = i + 1; j < nums.length; j++) {
                if(nums[i] + nums[j] == target) {
                    return new int[] {i, j};
                }
            }
        }
        return new int[] {};
    }
}

Solution #2:
The bruiteforce approach takes about O(n^2), but what we can do is.
We can find nextDigit by subtracting the num[i] from target value.

ex:
Input: nums = [3,2,4], target = 6
here,
the target is 6,
so during traversing of nums array,
we can subtract nums[i]
so nextDigit = target - nums[i];
when, i = 0, = 6 - 3 = 3

So we need to find out 3 value on the next indexes.
In order to do this,
We can keep all the values in the hashMap and simply find out the nextDigit value on o(1). If it matches then we have the next first and next index.

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