承接网站建设 优帮云,国产做的视频网站,音乐网站的建设,国外做家纺的网站双指针 1.移动零2.盛最多水的容器3.三数之和 1.移动零
给定一个数组 nums#xff0c;编写一个函数将所有 0 移动到数组的末尾#xff0c;同时保持非零元素的相对顺序。
// 题解#xff1a;使用双指针#xff0c;其中快指针指向非零元素#xff0c;慢指针指向首个零元素下… 双指针 1.移动零2.盛最多水的容器3.三数之和 1.移动零
给定一个数组 nums编写一个函数将所有 0 移动到数组的末尾同时保持非零元素的相对顺序。
// 题解使用双指针其中快指针指向非零元素慢指针指向首个零元素下标
void moveZeroes(vectorint nums) {int slowIdx 0;for (int fastIdx 0; fastIdx nums.size(); fastIdx) {if (nums[fastIdx] ! 0) {std::swap(nums[slowIdx], nums[fastIdx]);}}
}2.盛最多水的容器
给定一个长度为 n 的整数数组 height 。有 n 条垂线第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。找出其中的两条线使得它们与 x 轴共同构成的容器可以容纳最多的水。返回容器可以储存的最大水量。
// 题解面积公式 area std::min(height[i], height[j]) * (j - i)
// 指针从两端向内部移动当长板向内移动时短板会变小或者不变面积一定变小当短板向内移动时短板可能会变大面积也有可能变大因此只需要不断移动短板便可遍历得到最大面积
int maxArea(vectorint height) {int left_idx 0;int right_idx height.size() - 1;int area 0;while (left_idx right_idx) {// 需要注意下标是先使用后自增或者自减area height[left_idx] height[right_idx] ?std::max(area, (right_idx - left_idx) * height[left_idx]) :std::max(area, (right_idx - left_idx) * height[right_idx--]);}return area;
}3.三数之和
给你一个整数数组 nums 判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i ! j、i ! k 且 j ! k 同时还满足 nums[i] nums[j] nums[k] 0 。请你返回所有和为 0 且不重复的三元组。
// 题解双指针重复查询
// 排序数组从前向后逐步遍历数据按照双指针遍历内部数据构建三元组形式需要注意的是如何正确去重元素
vectorvectorint threeSum(vectorint nums) {if (nums.empty()) {return vectorvectorint();}std::sort(nums.begin(), nums.end());vectorvectorint results;for (int i 0; i nums.size(); i) {if (nums[i] 0) {return results;}// 去除重复数据if (i 0 nums[i] nums[i - 1]) continue;int left 0;int right nums.size() - 1;while (left right) {int target nums[left] nums[right] nums[i];if (target 0) {right--;} else if (target 0) {left;} else {results.push_bakc({nums[i], nums[left], nums[right]});// 数组内部去除重复数据while (left right nums[left] nums[left 1]) left;while (left right nums[right] nums[right - 1]) right--;// 更新新的下标left--;right;}}}return results;
}
