C++ 前缀和、双指针

前缀和代码分析：

第一步：预处理

function initPrefixSum(a, sum, size)

  sum[0]  = a[0];

  for i -> (1, size-1)

       sum[i] = sum[i-1] + a[i];

第二步：查询

function getPartialSum(sum, l, r)

  if l==0

     return sum[r]

return sum[r] - sum[l-1]

第一次-内存优化：

function initPrefixSum(a, size)

  for i -> (1, size-1)

       a[i] = a[i-1] + a[i];

代码练习 1 对应力扣 一维数组的动态和，代码见下

class Solution {
public:
    vector<int> runningSum(vector<int>& nums) {
        vector<int> runningSum;
        runningSum.push_back(nums[0]);
        for(int i=1; i<nums.size(); ++i){
            int x = runningSum[i-1] + nums[i];
            runningSum.push_back(x);
        }
        return runningSum;
    }
};

代码练习 2 对应力扣 找到数组的中间位置 代码见下

class Solution {
public:
    int findMiddleIndex(vector<int>& nums) {
        int sum[210];
        int n = nums.size();
        sum[0] = nums[0];
        for(int i = 1; i < n; ++i){
            sum[i] = sum[i-1] + nums[i];
        }
        for(int i = 0; i < nums.size(); ++i){
            int middleIndex = i;
            int a = 0, b = 0;
            if(middleIndex)
               a = sum[middleIndex - 1];
            b = sum[n-1] - sum[middleIndex];
            if(a == b){
                return middleIndex;
            }
        }
        return -1;
    }
};

代码练习，对应力扣，寻找数组的中心下标，代码见下

class Solution {
public:
    int pivotIndex(vector<int>& nums) {
        int n = nums.size();
        for(int i = 1; i < n; ++i){
            nums[i] += nums[i-1];
        }
        for(int i = 0; i < nums.size(); ++i){
            int middleIndex = i;
            int a = 0, b = 0;
            if(middleIndex)
               a = nums[middleIndex - 1];
            b = nums[n-1] - nums[middleIndex];
            if(a == b){
                return middleIndex;
            }
        }
        return -1;
    }
};

双指针：

快慢指针：就是两个指针，从同一侧开始遍历序列，移动步长一个快一个慢。常见应用有，链表判环，获取链表中间结点，删除有序数组重复项。

对撞指针：是指两个指针，分别指向序列的第一个元素和最后一个元素，然后指针相向移动，一个指针递增一个指针递减，直到两个指针值相撞或者满足其他特殊条件为止。常见应用有，两数之和，回文串判定，字符串的反转等等

分离双指针：两个指针分别属于不同的数组（或链表），两个指针分别在两个数组（或链表）中移动，从而解决相关算法问题，常见应用，有序数组合并，归并排序中的合并部分，对两数组求交集和并集。这个的优点便可以降低时间复杂度。

代码分析：

求链表的中点

function middleNode(head)

  slow=fast=head

  while fast and fast.next

    slow = slow.next

    fast = fast.next.next

return slow

数组中移除元素

function removeElement(arr, n, val)

  l = 0

  r = n - 1

  while(l <= r)

    if(arr[l] == val)

       arr[l] = arr[r]

       r -= 1

    else

      l += 1

return l

代码练习，对应蓝桥云课 回文判定 代码见下

#include <iostream>
#include<string>
using namespace std;
int main()
{
  string s;
  cin >> s;
  int i = 0;
  int j = s.size() - 1;
  while(i < j){
    if(s[i] != s[j]){
      break;
    }
    i += 1;
    j -= 1;
  }
  if(i >= j){
    cout << 'Y' << endl;
  }else{
    cout << 'N' << endl;
  }
  // 请在此输入您的代码
  return 0;
}

代码练习，对应蓝桥云课 反转字符串中的字符，代码见下

#include <iostream>
#include <string.h>
using namespace std;

char s[1000];

int main()
{
  cin.getline(s, 101, '\n');
  int i = 0;
  int j = strlen(s) - 1;
  while(i < j){
    swap(s[i], s[j]);
    i += 1;
    j -= 1;
  }
  cout << s << endl;
  // 请在此输入您的代码
  return 0;
}

代码练习，对应蓝桥云课 等腰三角形 代码见下

#include <iostream>
#include <algorithm>
using namespace std;

#define maxn 200001
int A[maxn], B[maxn], C[maxn];
int n;

int main()
{
  cin >> n;
  for(int i=0; i<n; ++i){
    cin >> A[i];
    C[i] = 2 * A[i];
  }
  for(int i=0; i<n; ++i){
    cin >> B[i];
  }
  sort(C, C+n);
  sort(B, B+n);
  int i=0, j=0, ans=0;
  while(i < n && j < n){
    if(C[i] > B[j]){
      j += 1;
      ans += 1;
    }
    i += 1;
  }
  cout << ans << endl;
  // 请在此输入您的代码
  return 0;
}