16 Array_and_string: Two-pointer Technique

[zwkcoding]

• Reverse the elements in an array code:

  void reverse(int* v, int N)  {
  int i = 0;
  int j = N - 1;
  while(i < j )  {
  swap(v[i], v[j]);
  i++;
  j--;
  }
  }

• Remove Element In-place code:

  ///O = O(N)
  int removeElement(vector<int>& nums, int val)  {
  int k = 0;
  for(int i = 0; i < nums.size(); i++)  {
      if (nums[i] != val)  {
          nums[k] = nums[i];
          k++;
      }
  }
  return k;
  }

• Two Sum II - Input array is sorted code:

  /// O = O(N)
  /// T = T(1)
  class Solution {
  public:
  vector<int> twoSum(vector<int>& numbers, int target) {
      int i = 0;
      int j = numbers.size() - 1;
      int tmp = 0;
      vector<int> res;
      while(i < j)  {
          tmp = numbers[i] + numbers[j];
          if(tmp == target)  {
              res.push_back(i+1);
              res.push_back(j+1);
              return res;
          } else if(tmp < target)  {
              i++;
          } else  {
              j--;
          }
  
      }
      return res;
  
  }
  };

Summary: use two-pointer when:

• iterate the array from two ends to the middle
• often used in a sorted array
• One slow-runner and one fast-runner at the same time.
  • The key is to determine the movement strategy for both pointers