绿色网站风格,上海微信网站建设公司,阳原网站建设,推广关键词如何优化重刷一遍相向双指针
题目 leetcode15
https://leetcode.cn/problems/3sum/
类似的题目还有leetcode16
leetcode16 解答思路
关键点
快排 双指针
1#xff1a; 快速排序#xff0c;之后使用双指针遍历对应的位置#xff0c;求解 2#xff1a; 主要是在确定了第一个值…重刷一遍相向双指针
题目 leetcode15
https://leetcode.cn/problems/3sum/
类似的题目还有leetcode16
leetcode16 解答思路
关键点
快排 双指针
1 快速排序之后使用双指针遍历对应的位置求解 2 主要是在确定了第一个值后通过双指针的方式确定出来其余两个值 3 将结果统计出来 4 返回的结果数量是可以看做是对于numsSize的组合 C^2_{numsSize}CnumsSize2 但是为什么不是C^3_{numsSize}CnumsSize3呢 因为在确定前两个数值后最后一个数值是固定的。所以是C^2_{numsSize}CnumsSize2
C语言代码范例 其实可以在nums[i] nums[left] nums[right] 0的情况下也添加快速过滤。提高代码运行效率。 C语言主要掌握的是二维malloc数组的申请和二级指针的内存申请。
/*** Return an array of arrays of size *returnSize.* The sizes of the arrays are returned as *returnColumnSizes array.* Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().*/int cmp(void *a, void *b)
{return *(int *)a - *(int *)b;
}int** threeSum(int* nums, int numsSize, int* returnSize, int** returnColumnSizes){qsort(nums, numsSize, sizeof(int), cmp);int **res (int **)malloc(sizeof(int *) * numsSize * numsSize);int i;int left;int right;int resSizeTmp 0;int left_record;int right_record;for (i 0; i numsSize - 2; i) {if (i 0 nums[i] nums[i - 1]) {continue;}left i 1;right numsSize - 1;if (nums[i] nums[left] nums[left 1] 0) {break;}while (left right) {if (nums[i] nums[left] nums[right] 0) {right--;} else if (nums[i] nums[left] nums[right] 0) {left;} else {res[resSizeTmp] (int *)malloc(sizeof(int) * 3);res[resSizeTmp][0] nums[i];res[resSizeTmp][1] nums[left];res[resSizeTmp][2] nums[right];resSizeTmp;// 存储数据后迅速过滤所有重复数据while(left right nums[left] nums[left]);while(left right nums[right] nums[--right]);}left_record nums[left];right_record nums[right];}}*returnSize resSizeTmp;*returnColumnSizes (int *)malloc(sizeof(int) * resSizeTmp);for (int i 0; i resSizeTmp; i) {(*returnColumnSizes)[i] 3;}return res;
}C 做法思路与C语言相似学习一下vector的用法 用sort函数进行排序。
#include iostream
using namespace std;
class Solution {
public:vectorvectorint threeSum(vectorint nums) {int n nums.size();sort(nums.begin(), nums.end());int i;int left;int right;vectorvectorint res;for (i 0; i n - 2; i) {if (i 0 nums[i] nums[i - 1]){ continue;}left i 1;right n - 1;while (left right) {int sum nums[i] nums[left] nums[right];if (sum 0) {vectorint tmp;tmp.push_back(nums[i]);tmp.push_back(nums[left]);tmp.push_back(nums[right]);res.push_back(tmp);while(left right nums[left] nums[left]);while(left right nums[right] nums[--right]);} else if (sum 0) {left;} else {right--;}}}return res;}
};
