Given an array of integers nums and a target value target, find the two integers in the array and return their array subscripts. You can assume that there is only one answer for each type of input. However, the same element in an array cannot be used twice.
1. Violence
Idea: Double loop through the number group
class Solution {
public int[] twoSum(int[] nums, int target) {
for (int i = 0; i < nums.length-1; 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"); }}Copy the code
2. Hash twice
For the first time, all the values are stored in the hash table. For the second time, the values are directly compared
class Solution {
public int[] twoSum(int[] nums, int target) {
// Use hash table time complexity O (n)
Map<Integer,Integer> map = new HashMap<>();
for (int i=0; i<nums.length; i++) {
map.put(nums[i],i);
}
for (int i=0; i<nums.length; i++) {
Integer position = target - nums[i];
if(map.containsKey(position) && i ! = map.get(position)) {return new int[]{i,map.get(position)}; }}throw new RuntimeException("No legitimate data was found."); }}Copy the code
3. Hash again
When putting the data into the hash table, it checks whether the data matching the conditions exists in the hash table
class Solution {
public int[] twoSum(int[] nums, int target) {
// Use hash table time complexity O (n)
Map<Integer,Integer> map = new HashMap<>();
for (int i=0; i<nums.length; i++) {
int position = target - nums[i];
if (map.containsKey(position)){
return new int[]{i,map.get(position)};
}
map.put(nums[i],i);
}
throw new RuntimeException("No legitimate data was found."); }}Copy the code