This question is taken from 1. Two Sum - LeetCode.

Naive Approach

Pick any element from the array and find another element that add up to produce target by traversing the array. Do it for every single element until we found our desired numbers and return their indices.

This approach has time complexity of O(n^2) and space complexity O(1).

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

        int[] ans = new int[2];

        // Pick an element 
        for(int i=0; i<nums.length; i++) 
        {
            // traverse other elements
            for(int j= i+1; j<nums.length; j++) 
            {
                // check whether they sums up to target
                if(nums[i] + nums[j] == target) 
                {
                    ans[0] = i;
                    ans[1] = j;

                    return ans;
                }
            }
        }

        return ans;
    }
}

Better Approach

We use HashMap in this case with key as the array numbers and values as their respective index. First we fill the HashMap with key and value as stated earlier. Then we traverse the array and pick a number one by one. Let's say the number is x. Now we need to find target - x (say y) in the array and we can do this in O(1) by using the HashMap. If y is found then we return the index of x and y otherwise we keep on picking x and finding y until their sum is target.

Time complexity for this approach is O(n), for traversing the array and space complexity is also O(n), for HashMap.

class Solution {
    public int[] twoSum(int[] nums, int target) {
        //<value, index>
        HashMap<Integer, Integer> mp = new HashMap<>();

        // fill hashmap
        for(int i=0; i<nums.length; i++)
        {
            mp.put(nums[i], i); 
        }

        int[] ans = new int[2];

        for(int i=0; i<nums.length; i++)
        {
            int key = target - nums[i];

            if(mp.containsKey(key) == true) // another element found
            {
                int j = mp.get(key);
                if(i != j)
                {
                    ans[0] = i;
                    ans[1] = j;
                    break;   
                }
            }
        }

        return ans;
    }
}