3. 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.

Examples

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]

Code

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] result = new int[2];
        for (int index = 0; index < nums.length; index++) {
            for (int innerIndex = 0; innerIndex < nums.length; innerIndex++) {
                if (index != innerIndex && (nums[index] + nums[innerIndex] == target)) {
                    result[0] = index;
                    result[1] = innerIndex;
                    return result;
                }
            }
        }  
        return result;
    }
}

• An integer array named result is initialized with a size of 2. This array will eventually hold the indices of the two numbers that sum to the target.

• The method uses a nested loop to iterate through the nums array:

  • The outer loop (index) goes through each element of the array.

  • The inner loop (innerIndex) also goes through the entire array.

• Inside the inner loop, the code checks two conditions:

  • index != innerIndex: Ensures that the same element is not used twice.

  • (nums[index] + nums[innerIndex] == target): Checks if the sum of the two elements at the current indices equals the target.

• If a valid pair is found, the indices of these elements are stored in the result array. The method then immediately returns the result array, exiting the method.

• If the loops complete without finding any valid pairs, the method returns the result array, which would contain the default values (both indices as 0), since it was initialized with no specific values.

This approach uses a brute-force method with a nested loop to check every possible pair of elements in the nums array to see if they sum to the target.

The above solution when executed took 119ms of time to be executed. While this is straightforward, it has a time complexity of O(n²), where n is the length of the nums array. This means it can be inefficient for large arrays. To enhance efficiency, a more optimal solution can be achieved using a HashMap, allowing for a time complexity of O(n). The HashMap would store each number and its index, allowing the program to find the complement of the current number (i.e., target - nums[index]) in constant time.

Code: Using Hashmap

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

• A HashMap called numberMap is created. This map will store numbers from the nums array as keys and their corresponding indices as values.

• A loop iterates through each element in the nums array. For each number (nums[index]), the code calculates the difference as target - nums[index]. This represents the value needed to reach the target when added to the current number.

• The method checks if difference is already a key in numberMap. If it is found, it means that there exists a number previously encountered that, when added to the current number (nums[index]), equals the target. The method then returns an array containing:

  • The index of the number that matches the difference (numberMap.get(difference)).

  • The current index (index).

• If the difference is not found in the map, the current number and its index are added to numberMap. This allows the program to keep track of previously encountered numbers for future lookups.

• If the loop completes without finding any valid pairs, the method returns an empty array. This indicates that no two indices were found that satisfy the condition.