Topic content:

Given an array of integers nums and a target value target, find the two integers in the array and the target values 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.

Solution:

If there is an example where two numbers add up to the result, then this example is the answer:

// Take c as an example:

int* twoSum(int* nums, int numsSize, int target, int* returnSize){
    int* res = (int *)malloc(sizeof(int) * 2);
    for(int i = 0; i < numsSize-1; i++) {
        for(int j = i + 1; j < numsSize; j++) {
            if(nums[i] + nums [j] == target) {
                res[0] = i;
                res[1] = j;
                *returnSize = 2;
                return res;
            }
        }       
    }
    return res;
}
Copy the code

However, this method is not recommended because of its high time complexity.

2. Repeat the loop + hash table solution

// Take Java as an example:

class Solution { public int[] twoSum(int[] nums, int target) { Map<Integer, Integer> map = new HashMap<>(); for (int i = 0; i < nums.length; i++) { int complement = target - nums[i]; if (map.containsKey(complement)) { return new int[] { map.get(complement), i }; } map.put(nums[i], i); } throw new IllegalArgumentException("No two sum solution"); }}Copy the code

This is a way of exchanging space for time. The logic simplifies the for loop by converting two for loops to one, and then looking up the table (the time complexity of two for loops is O(n ^2), the time complexity of one for loop is O(n), and the time complexity of hash table operation is O(1)).

conclusion

When it comes to lookup or traversal, don’t use violence loops if you can hash tables.