two pointers

투 포인터는 배열과 문자열 문제를 해결하는데 일반적으로 사용되는 기술이다.

일반적으로 왼쪽과 오른쪽 두 개의 인덱스를 이용하여 문제를 해결한다.

1. 시작 포인터는 0, 끝 포인터는 input의 length-1의 값으로 세팅한다.
2. 각 포인터가 같아질 때 까지 loop를 돈다.
3. loop가 반복될 때마다 포인터는 서로 향해 이동한다. 시작 포인터의 index는 증가하고 끝 포인터의 index는 감소한다.

문자열 대칭 관련된 문제

bool checkIfPalindrome(string s) {
    int left = 0;
    int right = s.size() - 1;
    
    while (left < right) {
        if (s[left] != s[right]) {
            return false;
        }
        left++;
        right--;
    }
    
    return true;
}

타겟 숫자 찾기

bool checkForTarget(vector<int>& nums, int target) {
    int left = 0;
    int right = nums.size() - 1;
    while (left < right) {
        int curr = nums[left] + nums[right];
        if (curr == target) {
            return true;
        }
        if (curr > target) {
            right--;
        } else {
            left++;
        }
    }

    return false;
}

특수한 상황일 경우 pointer를 다르게 구성하여 사용할 수 있다.

두 개의 배열 sorting
arr1: 1, 4, 7, 20, 38
arr2: 3, 5, 6, 17

vector<int> combine(vector<int>& arr1, vector<int>& arr2) {
    vector<int> ans;
    int i = 0, j = 0;
    while (i < arr1.size() && j < arr2.size()) {
        if (arr1[i] < arr2[j]) {
            ans.push_back(arr1[i]);
            i++;
        } else {
            ans.push_back(arr2[j]);
            j++;
        }
    }
    
    while (i < arr1.size()) {
        ans.push_back(arr1[i]);
        i++;
    }
    
    while (j < arr2.size()) {
        ans.push_back(arr2[j]);
        j++;
    }
    
    return ans;
}

Example 4: 392. Is Subsequence.(leetcode)

Given two strings s and t, return true if s is a subsequence of t, or false otherwise.

A subsequence of a string is a new string that is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (i.e., "ace" is a subsequence of "abcde" while "aec" is not).

   bool isSubsequence(string s, string t) {
        int i = 0, j = 0;
        while (i < s.size() && j < t.size()) {
            if (s[i] == t[j]) {
                i++;
            }
            j++;
        }
        
        return i == s.size();
    }