网站模板 源码之家,网站开发与维护是什么,wordpress怎么首页添加板块,30岁转行做网站设计审题#xff1a; 需要我们找到满足以下三个条件的所有三元组#xff0c;并存在二维数组中返回 1.三个元素相加为0 2.三个元素的下标不可相同 3.三元组的元素不可相同 思路#xff1a; 混乱的数据不利于进行操作#xff0c;所以我们先进行排序 我们可以采取枚举的方法进行解… 审题 需要我们找到满足以下三个条件的所有三元组并存在二维数组中返回 1.三个元素相加为0 2.三个元素的下标不可相同 3.三元组的元素不可相同 思路 混乱的数据不利于进行操作所以我们先进行排序 我们可以采取枚举的方法进行解题 首先最容易想到的就是三个for循环 每个循环确定一个元素遍历后在最深的第三层循环进行判断如果满足相加为0就把对应数据存入二维数组 不过根据第二点三个元素的下标不可相同 我们需要避免出现一个三元组中同一个位置的元素被用两次 egnums[0] nums[0] nums[1] 有 a第一层循环的元素下标 b第二层循环的元素下标 c第三层循环的元素下标 不过此时我们的时间复杂度有点高ON^3 如何优化 假设num1,2,3分别是三元组的值有num1num2num3 0 我们先定住num1不变num2越大num3就越小也就是说我们可以让第三层循环从n-1开始从右向左循环这样子可以更快找到满足条件的值 此时第二三层循环的时间复杂度就变成了ON我们此时可以换一种方法写后面两层循环 这个方法就是我们常说的「双指针」当我们需要枚举数组中的两个元素时如果我们发现随着第一个元素的递增第二个元素是递减的那么就可以使用双指针的方法。 总结一下遍历方法为第一层循环双指针代替第二三层循环 解题 1预处理 2第一层循环 第一层循环的作用是确定第一个元素值且根据第三点我们不能有重复数据一旦当前的值和前一个是一样的则直接continue到下一个索引位置 3双指针 目标条件判断方法:由于已经确定了第一个元素的值所以根据三者之和为0可以得知后面两个元素之和为-num1即为满足条件 遍历过程中若满足条件就把元素插入二维数组插入后移动双指针因为此前移动过left和right所以要再满足left right的条件移动后判断是否满足和前一个元素不同的条件不满足就循坏更新直到满足。 若不满足条件 和大于target要让和变小right-- 和小于target要让和变大left 最后返回answer即可 15. 三数之和 - 力扣LeetCode
