【解法2】优化解：多指针法
← 内容总览 07 / 24 下一节 → 原始讲义 · 非增强校订版 · 原书检索 · 文字用于定位，公式与图表请回原页核验 · 本次导入快照
## 【解法2】优化解：多指针法
(1)用指针i,j维护一个窗口，其和 current\_sum <= k。固定左端点i，向右移动右端点j直到窗口和将要超过 k。此时，以i为起点的所有合法子序列有i-i+1个。然后将i右移一位，继续该过程。
(2) 伪代码如下：
<!-- verified-by-hand -->
> [!success] 已结合原文第 44 页及 Markdown 上下文人工校对
> m 和‘章 s ka’为水印，while 的两条语句需同属一个块。
int ans ( int A [], int n , int k )
{
int count = 0 , sum = 0 , i = 0 ;
for ( int j = 0 ; j & lt ; n ; j ++ )
{
sum += A [ j ];
while ( sum & gt ; k )
{
sum -= A [ i ];
i ++ ;
}
count += j - i + 1 ;
}
return count ;
}
int ans ( int A [], int B [], int n )
{
int pair_count = 0 ;
int count [ 5 * n + 1 ], s [ 5 * n + 1 ];
for ( int i = 0 ; i & lt ; = 5 * n ; i ++ ) count [ i ] = 0 ;
for ( int i = 0 ; i & lt ; n ; i ++ )
if ( A [ i ] & lt ; = 5 * n ) count [ A [ i ]] ++ ;
s [ 0 ] = count [ 0 ];
for ( int i = 1 ; i & lt ; = 5 * n ; i ++ )
s [ i ] = s [ i - 1 ] + count [ i ];
for ( int j = 0 ; j & lt ; n ; j ++ )
if ( B [ j ] & lt ; = 5 * n ) pair_count += s [ 5 * n - B [ j ]];
return pair_count ;
}
int ans ( int A [], int B [], int n )
{
int t = 0 ;
for ( int i = 0 ; i & lt ; n ; i ++ )
for ( int j = 0 ; j & lt ; n ; j ++ )
if ( A [ i ] + B [ j ] & lt ; = 5 * n ) t ++ ;
return t ;
}
( 3 ) // 时间复杂度：O(n²) 空间复杂度：O(1)
( 3 ) // 时间复杂度：O(n) 空间复杂度：O(n)
//快速排序 void Qsort(int A[], int L, int R)
{
if ( L & gt ; = R ) return ; //区间内元素个数为0或 1，自然有序，递归
终止
int i = L , j = R ;
int pivot = A [ L ]; //选取区间第一个元素作为基准
// 不断交换左边比 pivot 大的数和右边比 pivot 小的数
while ( i & lt ; j )
{
while ( i & lt ; j & amp ; & amp ; A [ j ] & gt ; = pivot ) j -- ; // 从右向左找第一个小于 pivot 的数
三 while ( i & lt ; j & amp ; & amp ; A [ i ] & lt ; = pivot ) i ++ ; // 从左向右找第一个大于 pivot的数
if ( i & lt ; j ) swap ( A [ i ], A [ j ]);
}
//将基准值 A[L] 与 A[i] 交换
swap ( A [ L ], A [ i ]);
//递归处理左右两个子区间
Qsort ( A , L , i - 1 );
Qsort ( A , i + 1 , R );
}
int ans ( int A [], int n , int k )
{
Qsort ( A , 0 , n -1 );
return A [ k -1 ];
}
时间复杂度 ： O ( nlogn ) 空间复杂度 ： O ( logn )
int ans ( int A [], int n , int k )
{
int count [ 2 * n ];
for ( int i = 0 ; i & lt ; 2 * n ; i ++ ) count [ i ] = 0 ; // 初始化count数组
for ( int i = 0 ; i & lt ; n ; i ++ ) count [ A [ i ]] ++ ;
for ( int i = 0 ; i & lt ; 2 * n ; i ++ )
{
k = k - count [ i ];
if ( k & lt ; = 0 ) return i ;
} }
( 3 ) // 时间复杂度：O(n) 空间复杂度：O(n)
//快速排序
void Qsort ( int A [], int L , int R )
{
if ( L & gt ; = R ) return ; //区间内元素个数为 0或 1，自然有序，递归
终止
int i = L , j = R ;
int pivot = A [ L ]; //选取区间第一个元素作为基准
// 不断交换左边比 pivot 大的数和右边比 pivot 小的数
while ( i & lt ; j )
{
while ( i & lt ; j & amp ; & amp ; A [ j ] & gt ; = pivot ) j -- ; // 从右向左找第一个小于 pivot 的数
while ( i & lt ; j & amp ; & amp ; A [ i ] & lt ; = pivot ) i ++ ; // 从左向右找第一个大于 pivot 的数
if ( i & lt ; j ) swap ( A [ i ], A [ j ]);
}
//将基准值 A[L] 与 A[i] 交换
swap ( A [ L ], A [ i ]);
//递归处理左右两个子区间
Qsort ( A , L , i - 1 );
Qsort ( A , i + 1 , R );
}
void ans ( int A [], int n )
{
Qsort ( A , 0 , n -1 ); // 览机考研
for ( int i = 0 ; i & lt ; n ; i ++ )
if ( i == 0 | l A [ i ] != A [ i -1 ]) // A[i]这个元素第一次出现则输出
printf ( & quot ; % d & quot ;, A [ i ]);
}
( 3 ) // 时间复杂度：O(nlogn) 空间复杂度：O(logn)
void ans ( int A [], int n )
{
int count [ n ] = { 0 };
for ( int i = 0 ; i & lt ; n ; i ++ )
count [ A [ i ] -2 * n ] ++ ; // 统计 A 中每个元素出现次数
for ( int i = 0 ; i & lt ; n ; i ++ )
if ( count [ i ] & gt ; 0 )
printf ( & quot ; % d & quot ;, i + 2 * n ); // 若 count[i]>0 说明 i+2n 出现过
}
int ans ( int A [], int n , int k )
{
int m ; // m是本次遍历选择元素数
int m_max = 0 ; // m_max初值为0
for ( int i = 0 ; i & lt ; n ; i ++ ){ // A[i]为本次枚举最小元素
m = 0 ; // 每次枚举时都需要清空m
for ( int j = 0 ; j & lt ; n ; j ++ )
if ( A [ j ] & gt ; = A [ i ] & amp ; & amp ; A [ j ] & lt ; = A [ i ] + k )
m ++ ; // A[j]处于选择范围则m++
m_max = max ( m_max , m ); //如果m大则更新m_max
}
return m_max ; //输出最大m值
}
( 3 ) // 时间复杂度：O(n²) 空间复杂度：O(1)
int ans ( int A [], int n , int k )
{
Qsort ( A , 0 , n - 1 );
int m_max = 0 , j = 0 ;
for ( int i = 0 ; i & lt ; n ; i ++ )
{
if ( j & lt ; i ) j = i ;
while ( j + 1 & lt ; n & amp ; & amp ; A [ j + 1 ] & lt ; = A [ i ] + k ) j ++ ;
m_max = max ( m_max , j - i + 1 );
}
return m_max ;
}
int ans ( int A [], int n , int k )
{
int m = 0 ; // m 是本次取值范围为 L~R 选择元素数
om
int m_max = 0 ; // m_max 初值为 0
int B [ maxn ]; an
memset ( B , 0 , sizeof ( B ));
for ( int i = 0 ; i & lt ; n ; i ++ ) B [ A [ i ]] ++ ; // A[i]出现次数+1
int L = 0 , R = 0 ;
for ( R = 0 ; R & lt ; n ; R ++ )
{
m += B [ R ]; // m 加上 B[R]
if ( R - L & gt ; k )
{ // 如果范围差大于 k 则 L 右移
m -= B [ L ]; // 此时范围是[L+1,R]，m 减去 B[L]
L ++ ;
}
m_max = max ( m_max , m ); // 如果 m 大则更新 m_max
}
return m_max ; // 输出最大m值
}
← 内容总览 07 / 24 下一节 →