LeetCode Solution 1. 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]
Output: 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]Constraints:
2 <= nums.length <= 105-109 <= nums[i] <= 109-109 <= target <= 109
SOLUTION 1:(One-pass hash table)
The optimal solution to solve this problem is using a HashMap. For each element of the array, (target-nums[i]) and the index are stored in the HashMap.
class Solution {
public int[] twoSum(int[] nums, int target) {
if(nums==null || nums.length<2)
return new int[]{0,0};
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
for(int i=0; i<nums.length; i++){
if(map.containsKey(nums[i])){
return new int[]{map.get(nums[i]), i};
}else{
map.put(target-nums[i], i);
}
}
return new int[]{0,0};
}
}Time complexity of this algorithm being O(n).
Using the one-pass hash Table:
The one-pass hash table .While we iterate and insert the values in the table .We also look back at the hash map to check if the complement of the value is already present in the hash table. If it exists then the 2 numbers which form the sum which is equal to the target is returned.
Solution 2:(Brute force)
The brute force method is really simple.We iterate through all the elements of the array ,If there is any other value where target-x is equal to 0 then it returns the indices the array.
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[j] == target - nums[i]) {
return new int[] { i, j };
}
}
}
throw new IllegalArgumentException("No two sum solution");
}
}Time complexity of this algorithm being O(n²).
Related post:
