京东客网站怎么做,wordpress 新浪主题,长沙代注册公司多少钱,北京做兼职网站有哪些1. 两数之和问题
力扣第1题就是两数之和问题#xff0c;给定一个整数数组 nums 和一个整数目标值 target#xff0c;请你在该数组中找出 和为目标值 target 的那两个整数#xff0c;并返回它们的数组下标。你可以假设每种输入只会对应一个答案。但是#xff0c;数组中同一…1. 两数之和问题
力扣第1题就是两数之和问题给定一个整数数组 nums 和一个整数目标值 target请你在该数组中找出 和为目标值 target 的那两个整数并返回它们的数组下标。你可以假设每种输入只会对应一个答案。但是数组中同一个元素在答案里不能重复出现。你可以按任意顺序返回答案。
第一种方法是用两层循环解决第一层for循环确定一个数第二层for循环确定第二个数这种方法虽然简单但是时间复杂度为 O ( n 2 ) O(n^2) O(n2),我们可以使用哈希表法来将寻找第二个数的时间复杂度降低从 O ( n ) O(n) O(n) 降到 O ( 1 ) O(1) O(1). const prevNums {}; // 存储出现过的数字和对应的索引 for (let i 0; i nums.length; i) { // 遍历元素 const curNum nums[i]; // 当前元素 const targetNum target - curNum; // 满足要求的目标元素 const targetNumIndex prevNums[targetNum]; // 在prevNums中获取目标元素的索引if (targetNumIndex ! undefined) { // 如果存在直接返回 [目标元素的索引,当前索引]return [targetNumIndex, i];} else { // 如果不存在说明之前没出现过目标元素prevNums[curNum] i; // 存入当前的元素和对应的索引}}拓展:发散思维一下如果返回的是两个值还可以用另外一种解法双指针法
// 双指针法
function twoSum(nums, target) {const hashTable [];const lengthOfNums nums.length;let first 0;let second lengthOfNums - 1;nums.sort((a, b) a - b);// 特判if (lengthOfNums 1) return null;while (first second) {if (nums[first] target) return null;// first和second枚举的值要与上一个不同if (nums[first] nums[second] target) {hashTable.push([nums[first], nums[second]])while (nums[first] nums[first 1]) first;while (nums[second] nums[second - 1]) second--;first;second--;}else if (nums[first] nums[second] target) second--;}return hashTable;
}2.三数之和问题
LeetCode15.给你一个包含 n 个整数的数组 nums判断 nums 中是否存在三个元素 abc 使得a b c 0请你找出所有和为 0 且不重复的三元组。注意答案中不可以包含重复的三元组。 分析 首先三层循环想都不要想时间复杂度太高了直接放弃。比较好的办法就是“排序双指针”。先将数组升序排序之后固定一位元素再用两数之和思想找剩下的两个元素。 function threeSum(nums) {const lengthOfNums nums.length;// 特判if (lengthOfNums 3 || nums null) {return [];}nums.sort((a, b) a - b);let bucket [];for (let first 0; first lengthOfNums; first) {// 如果排序好的数组的第一个元素都大于0那么就不会有三数之和等于0的情况if (nums[first] 0) {break;}// 为了避免得到重复结果需要和上一次枚举的数不相同if (first 0 nums[first] nums[first - 1]) continue;let second first 1;let third lengthOfNums - 1;while (second third) {const sumOfThreeNums nums[first] nums[second] nums[third];if (sumOfThreeNums 0) {bucket.push[[nums[first], nums[second], nums[third]]];while (second third nums[second] nums[second 1]) second; // 去重while (second third nums[third] nums[third - 1]) third--; // 去重second;third--;}else if (sumOfThreeNums 0) second;else third--;}}return bucket;
}
