Nuggets team number online, help you Offer rimmon! Click to see details

I. Topic Description:

Given an integer array nums and an integer target, find the two integers in the array whose sum is the target value and return their array indices.

You can assume that there is only one answer for each input. However, the same element in the array must not appear repeatedly in the answer.

You can return the answers in any order.

Example 1: input: nums = [2,7,11,15], target = 9 output: [0,1] description: because nums[0] + nums[1] == 9, [0,1] is returned.Copy the code

Ii. Thinking analysis:

  • Through the array
  • judge
  • Returns indexes that match the criteria

There are a variety of solutions to achieve this, such as double loop, hash table can be implemented

When iterating through the array to find target-x, note that every element before x already matches x, so no further matching is needed. Each element can’t be used twice, so we just look for target-x in the element after x

Three, AC code

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    for (let i=0; i<nums.length; i++) {
        var index = nums.indexOf(target-nums[i]);
        if (index !== -1 && index !== i) {
            return [i,index];
        }
    }
};
Copy the code

Four,

This seems like an easy one, so I’m just going to write it this way, double loop index

/** * @param {number[]} nums * @param {number} target * @return {number[]} */ var twoSum = function(nums, target) { var arr = []; for(var i = 0; i < nums.length-1; i++){ for(var j = i+1; j < nums.length; j++){ if (nums[i] + nums[j] == target){ arr.push(i); arr.push(j); } } } return arr; }; Input :[2,7,11,15] 9 output :[0,1] expected result :[0,1]Copy the code

You can do this, but if you double the time O(n^2), you increase the space complexity;

Execution time: 84 ms Memory: 37.9 MB

/** * @param {number[]} nums * @param {number} target * @return {number[]} */ var twoSum = function(nums, target) { for(var i = 0; i < nums.length-1; i++){ for(var j = i+1; j < nums.length; j++){ if (nums[i] + nums[j] == target){ return [i,j]; }}}};Copy the code

There is little difference in execution time and memory consumption compared to the above method

Some people also see the use of hash table, but it increases the time complexity and space complexity, JS is not recommended

For reference only

Refer to the topic

  • Force button (LeetCode)