双指针
(1)快慢双指针
适用于使用双指针进行元素移动,覆盖
(2)首尾双指针
计算区域面积,三数之和
1、移动0
(1)题目描述以及输入输出
( 1 ) 题目描述:
给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。
( 2 ) 输入输出描述:
输入: nums = [ 0,1 ,0,3,12]
输出: [ 1,3 ,12,0,0]
关键思路:
fast遍历数组,slow用于指向零。遍历时,不为0元素时,slow与fast进行swap( ) ,都会向右移动; 0 时,仅fast移动。
(2)代码块
class Solution {
public:
void moveZeroes( vector< int>& nums)
{
int slow = 0 ;
int fast = 0 ;
for( fast = 0 ; fast< nums.size( ) ; ++fast)
{
if( nums[ fast] != 0 )
swap( nums[ slow++] ,nums[ fast] ) ;
}
}
} ;
2、盛水最多的容器
(1)题目描述以及输入输出
( 1 ) 题目描述:
给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。
( 2 ) 输入输出描述:
输入:height = [ 1,1 ]
输出:1
关键思路:
首尾双指针while遍历数组,计算区域面积:( right-left) *min( height[ left] ,height[ right] )
接着偏移左右双指针,height[ left] < height[ right] ,left++,找高边缘。
(2)代码块
class Solution {
public:
int maxArea( vector< int>& height)
{
int left = 0 ;
int right = height.size( ) -1;
int result = 0 ;
while( left< right)
{
if( height[ left] < height[ right] )
{
result = max(( right-left) *height[ left] ,result) ;
left++;
}
else
{
result = max(( right-left) *height[ right] ,result) ;
right--;
}
}
return result;
}
} ;
3、三数之和
(1)题目描述以及输入输出
( 1 ) 题目描述:
给你一个整数数组 nums ,判断是否存在三元组 [ nums[ i] , nums[ j] , nums[ k] ] 满足 i != j、i != k 且 j != k ,同时还满足 nums[ i] + nums[ j] + nums[ k] == 0 。请你返回所有和为 0 且不重复的三元组。
( 2 ) 输入输出描述:
输入:nums = [ -1,0,1,2,-1,-4]
输出:[ [ -1,-1,2] ,[ -1,0,1] ]
关键思路:
遍历数组元素,遍历到该元素时先对元素进行去重,使用首尾双指针while计算三者相加的和,再进行首尾指针移动;
找到和为0的三元素后,插入结果,并对接下来的首尾指针进行去重,去重后指针均向中间移动。
(2)代码块
class Solution {
public:
vector< vector< int>> threeSum( vector< int>& nums)
{
sort( nums.begin( ) ,nums.end( )) ;
vector< vector< int>> result;
int left,right;
for( int i = 0 ; i< nums.size( ) ; ++i)
{
if( nums[ i] > 0 ) return result;
if (( i >= 1 ) && ( nums[i] == nums[i- 1 ])) continue ; // 首去重
left = i+1;
right = nums.size( ) -1;
while( left< right)
{
if( nums[ i] + nums[ left] + nums[ right] > 0 ) right--;
else if( nums[ i] + nums[ left] + nums[ right] < 0 ) left++;
else
{
result.push_back( vector< int> { 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 result;
}
} ;