首页 > 代码库 > 两指针--减少数组循环
两指针--减少数组循环
题目(lintcode)：
1.二数之和
2.三数之和
3.最接近的三数之和
4.四数之和
取三数之和为例：
（一）
普通算法，多重遍历数组，需要多重for嵌套，但严重超时。
（二）
剪枝，在外层循环中考虑有没有“不可能符合要求”的情况。
例如，在三数之和中，若两个数之和大于0，直接break。但题目没说不会出现负数，所以不对。
（三）
接（二），判断两个数之和大于0无效，是因为数组无序，所以先进行排序
sort(nums.begin(),nums.end());
之后可以在保证大于0时，break掉。像这样：
for (int i = 0; i < nums.size(); i++) { if (nums[i] > 0) break; for (int j = i;j < nums.size(); j++) { if (nums[j] >= 0 && nums[j] +nums[i] > 0) break; for (int k = j; k < nums.size(); k++) {
（四）
设置两个指针，分别指向“数组首”(front)和“数组尾”(rear)，计算两指针处的和，再加上for循环的一个数，得到三数和sum：
若sum大于零，使和变小，rear-- 即可；若sum小于零，使和变大，front++ 即可。
vector<vector<int> > threeSum(vector<int> &nums) { set<vector<int> > re; vector<int> in; sort(nums.begin(), nums.end(), greater<int>()); int front, rear, sum; for (int i = 0; i < nums.size(); i++) { front = 0; rear = nums.size() -1; while (front < rear) { if (front == i) front++; else if (rear == i) rear--; if (front == rear) break; sum = nums[front] + nums[rear] + nums[i]; if (sum == 0) { in.clear(); in.push_back(nums[front]); in.push_back(nums[rear]); in.push_back(nums[i]); sort(in.begin(), in.end()); re.insert(in); do {front++;} while (front < rear && nums[front] == nums[front - 1]); } else if (sum > 0) front++; else rear--; } } return vector <vector<int>>(re.begin(),re.end()); }
两指针--减少数组循环
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。