其實這題不在JS30天內,但這大概就基礎題中的基礎題吧
Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.
Follow-up: Can you come up with an algorithm that is less than O(n2) time complexity?
第一種解法算是最直覺的,只是我把跑兩次迴圈用一次跑完,不過就不符合Follow-up的小於O(n2),因為實際上還是算跑兩次迴圈
var twoSum = function(nums, target) {
for(let i=0,j=1;i<nums.length-1;j++){
if(nums[i]+nums[j]===target){
return [i,j]
}
if(j===nums.length){
j=++i;
}
}
};
第二種解法我在思考indexOf到底算不算迴圈的一種,嚴格來算應該算(笑,這個解法是找差值有沒有在陣列裡,並且不能為i,因為陣列有可能有相同數字的情況,不過這個順序就會不一樣
Ex: nums=[3,3],target=6,Expected會是[0,1],但我的output會是[1,0]
var twoSum = function(nums, target) {
for(let i=0;i<nums.length;i++){
let nextNum=target-nums[i];
let nextIndex=nums.indexOf(nextNum)
if(nextIndex!==i&&nextIndex!==-1){
return [i,nextIndex]
}
}
};
第三種解法是看到其他人的解法覺得蠻有趣的,其實跟第二種解法有點類似,只是是用物件來做,倒沒有想到還可以用物件做,不過有趣的是這種解法佔的記憶體是最多的(笑。
var twoSum = function(nums, target) {
const obj={};
for(let i=0;i<nums.length;i++){
let diffNum=target-nums[i];
if(diffNum in obj) return [i,obj[diffNum]];
obj[nums[i]]=i
}
};