leetcode - 兩數之和

題意

給定一個整數數組nums和一個整數目標值target，請你在該數組中找出 和為目標值 的那兩個 整數，并返回它們的數組下標。

你可以假設每種輸入只會對應一個答案。但是，數組中同一個元素不能使用兩遍。

你可以按任意順序返回答案。

示例

示例 1：

輸入：nums =?[2,7,11,15], target = 9
輸出：[0,1]
解釋：因為 nums[0]?+ nums[1]?== 9 ，返回?[0, 1]?。

示例 2：

輸入：nums =?[3,2,4], target = 6
輸出：[1,2]

示例 3：

輸入：nums =?[3,3], target = 6
輸出：[0,1]

提示：

• 2 <= nums.length <= 103

• -109 <= nums[i] <= 109

• -109 <= target <= 109

• 只會存在一個有效答案

題目出處

鏈接：https://leetcode-cn.com/problems/two-sum

思路

抓重點就是，在數組 nums 中找兩個元素使其與目標值 target 相等，規(guī)則是數組 nums 里面的每一個元素只能使用一次，為了讓程序更加容易通過，出題人限定了輸入的輸出答案有且僅有一個，而且不需要你考慮順序，你只需要返回其下標就好了。

最通用的手段，暴力破解嘛，兩層循環(huán)分別找出元素中的兩個值，如果與目標 target 值吻合就返回下標，退出程序。

代碼

/**
?*?@param?{number[]}?nums
?*?@param?{number}?target
?*?@return?{number[]}
?*/
const?twoSum?=?function?(nums,?target)?{
??for?(let?i?=?0;?i?????for?(let?j?=?i?+?1;?j???????if?(nums[i]?+?nums[j]?===?target)?{
????????return?[i,?j];
??????}
????}
??}
};

export?default?twoSum;

測試

腳本

import?twoSum?from?'../../code/leetcode/1';

describe('test?function?twoSum:',?()?=>?{
??test('test?case?nums?=?[3,?3],?target?=?6',?()?=>?{
????const?data?=?twoSum([3,?3],?6);
????expect(data).toEqual([0,?1]);
??});

??test('test?case?nums?=?[2,7,11,15],?target?=?9',?()?=>?{
????const?data?=?twoSum([2,?7,?11,?15],?9);
????expect(data).toEqual([0,?1]);
??});

??test('test?case?nums?=?[3,2,4],?target?=?6',?()?=>?{
????const?data?=?twoSum([3,?2,?4],?6);
????expect(data).toEqual([1,?2]);
??});
});

結果

????coding?git:(master)???npm?run?test

>[email protected]?test
>?jest

?PASS??test/leetcode/1.test.js
??test?function?twoSum:
??????test?case?nums?=?[3,?3],?target?=?6?(2?ms)
??????test?case?nums?=?[2,7,11,15],?target?=?9
??????test?case?nums?=?[3,2,4],?target?=?6?(1?ms)

Test?Suites:?1?passed,?1?total
Tests:???????3?passed,?3?total
Snapshots:???0?total
Time:????????0.545?s,?estimated?1?s
Ran?all?test?suites.
???coding?git:(master)??

思考

• 有沒有更好的解法

• 存在多個有效答案是什么情況？

• 按從小到大的順序返回是什么情況？

• 如果改成和為目標值的三個整數呢？

這里筆者象征性地提了幾個問題，供讀者們閱讀后思考，挖坑不填坑哈哈，歡迎在留言下方評論，分享你的見解和想法。

說明

本文首發(fā)于 GitHub 倉庫https://github.com/ataola/coding，線上閱讀地址：https://zhengjiangtao.cn/coding/，轉載請注明出處，謝謝！