給定一個(gè)整數(shù)數(shù)組 nums 和一個(gè)目標(biāo)值 target练慕，請(qǐng)你在該數(shù)組中找出和為目標(biāo)值的那兩個(gè)整數(shù)，并返回他們的數(shù)組下標(biāo)技掏。
示例:
- 給定 nums = [2, 7, 11, 15], target = 9
- 因?yàn)?nums[0] + nums[1] = 2 + 7 = 9
- 所以返回 [0, 1]
思路
- 使用一個(gè)map將遍歷過(guò)的數(shù)字存起來(lái)铃将，值作為key，下標(biāo)作為值哑梳。
- 對(duì)于每一次遍歷：
- 取map中查找是否有key為target-nums[i]的值
1.如果取到了劲阎，則條件成立，返回鸠真。
2.如果沒(méi)有取到悯仙，將當(dāng)前值作為key龄毡，下標(biāo)作為值存入map - 時(shí)間復(fù)雜度：O(n) 空間復(fù)雜度O(n)
var twoSum = function (nums, target) {
const map = {};
if (Array.isArray(nums)) {
for (let i = 0; i < nums.length; i++) {
if (map[target - nums[i]] != undefined) {
return [map[target - nums[i]], i];
} else {
map[nums[i]] = i;
}
}
}
return [];
};
給定一個(gè)包含 n 個(gè)整數(shù)的數(shù)組nums，判斷 nums 中是否存在三個(gè)元素a锡垄，b沦零，c ，使得 a + b + c = 0 货岭？找出所有滿足條件且不重復(fù)的三元組路操。
注意：答案中不可以包含重復(fù)的三元組。
例子
- 例如, 給定數(shù)組 nums = [-1, 0, 1, 2, -1, -4]千贯，
- 滿足要求的三元組集合為：
[
[-1, 0, 1],
[-1, -1, 2]
]
思路
題目中說(shuō)明可能會(huì)出現(xiàn)多組結(jié)果屯仗，所以我們要考慮好去重
1.為了方便去重，我們首先將數(shù)組排序
2.對(duì)數(shù)組進(jìn)行遍歷搔谴，取當(dāng)前遍歷的數(shù)nums[i]為一個(gè)基準(zhǔn)數(shù)魁袜，遍歷數(shù)后面的數(shù)組為尋找數(shù)組
3.在尋找數(shù)組中設(shè)定兩個(gè)起點(diǎn)，最左側(cè)的left(i+1)和最右側(cè)的right(length-1)
4.判斷nums[i] + nums[left] + nums[right]是否等于0敦第，如果等于0峰弹，加入結(jié)果，并分別將left和right移動(dòng)一位
5.如果結(jié)果大于0申尼，將right向左移動(dòng)一位垮卓，向結(jié)果逼近
5.如果結(jié)果小于0垫桂，將left向右移動(dòng)一位师幕，向結(jié)果逼近
** 注意整個(gè)過(guò)程中要考慮去重 **
var threeSum = function (nums) {
const result = [];
nums.sort((a, b) => a - b);
for (let i = 0; i < nums.length; i++) {
// 跳過(guò)重復(fù)數(shù)字
if (i && nums[i] === nums[i - 1]) { continue; }
let left = i + 1;
let right = nums.length - 1;
while (left < right) {
const sum = nums[i] + nums[left] + nums[right];
if (sum > 0) {
right--;
} else if (sum < 0) {
left++;
} else {
result.push([nums[i], nums[left++], nums[right--]]);
// 跳過(guò)重復(fù)數(shù)字
while (nums[left] === nums[left - 1]) {
left++;
}
// 跳過(guò)重復(fù)數(shù)字
while (nums[right] === nums[right + 1]) {
right--;
}
}
}
}
return result;
}
給定一個(gè)包含 n 個(gè)整數(shù)的數(shù)組nums，判斷 nums 中是否存在四個(gè)元素a诬滩，b霹粥，c，d 疼鸟，使得 a + b + c + d = 0 后控？找出所有滿足條件且不重復(fù)的四元組。
實(shí)例
注意：答案中不可以包含重復(fù)的四元組空镜。
給定數(shù)組 nums = [1, 0, -1, 0, -2, 2]浩淘，和 target = 0。
滿足要求的四元組集合為：
[
[-1, 0, 0, 1],
[-2, -1, 1, 2],
[-2, 0, 0, 2]
]
思路
你已經(jīng)經(jīng)歷了兩數(shù)之和吴攒、三數(shù)之和张抄，玩玩沒(méi)想到，還有四數(shù)之和...
其實(shí)洼怔，后面還有五數(shù)之和署惯，六數(shù)之和...
到這里其實(shí)我們就能發(fā)現(xiàn)一些規(guī)律，我們可以像[三數(shù)之和]那樣镣隶，我們可以通過(guò)大小指針來(lái)逼近結(jié)果极谊，從而達(dá)到降低一層時(shí)間復(fù)雜度的效果诡右。
不管是幾數(shù)之和，我們都用這種方法來(lái)進(jìn)行優(yōu)化轻猖。
var fourSum = function (nums, target) {
if (nums.length < 4) {
return [];
}
nums.sort((a, b) => a - b);
const result = [];
for (let i = 0; i < nums.length - 3; i++) {
if (i > 0 && nums[i] === nums[i - 1]) {
continue;
}
if (nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) {
break;
}
for (let j = i + 1; j < nums.length - 2; j++) {
if (j > i + 1 && nums[j] === nums[j - 1]) {
continue;
}
let left = j + 1,
right = nums.length - 1;
while (left < right) {
const sum = nums[i] + nums[j] + nums[left] + nums[right];
if (sum === target) {
result.push([nums[i], nums[j], nums[left], nums[right]]);
}
if (sum <= target) {
while (nums[left] === nums[++left]);
} else {
while (nums[right] === nums[--right]);
}
}
}
}
return result;
};
