darkan

// First Method
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size() - 1; // Define the target in the closed interval [left, right]
        while (left <= right) { // When left == right, the interval [left, right] is still valid, so use <=
            int middle = left + ((right - left) / 2); // Prevent overflow, equivalent to (left + right)/2
            if (nums[middle] > target) {
                right = middle - 1; // target is in the left interval, so [left, middle - 1]
            } else if (nums[middle] < target) {
                left = middle + 1; // target is in the right interval, so [middle + 1, right]
            } else { // nums[middle] == target
                return middle; // Found the target value in the array, return the index directly
            }
        }
        // Target value not found
        return -1;
    }
};

// Version Two
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size(); // Define the target in the closed left and open right interval, i.e., [left, right)
        while (left < right) { // Because when left == right, it is an invalid space in [left, right), so use <
            int middle = left + ((right - left) >> 1);
            if (nums[middle] > target) {
                right = middle; // target is in the left interval, in [left, middle)
            } else if (nums[middle] < target) {
                left = middle + 1; // target is in the right interval, in [middle + 1, right)
            } else { // nums[middle] == target
                return middle; // Found the target value in the array, return the index directly
            }
        }
        // Target value not found
        return -1;
    }
};

// Time complexity: O(n)
// Space complexity: O(1)
class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int slowIndex = 0;
        for (int fastIndex = 0; fastIndex < nums.size(); fastIndex++) {
            if (val != nums[fastIndex]) {
                nums[slowIndex++] = nums[fastIndex];
            }
        }
        return slowIndex;
    }
};

class Solution {
public:
    vector<int> sortedSquares(vector<int>& A) {
        int k = A.size() - 1;
        vector<int> result(A.size(), 0);
        for (int i = 0, j = A.size() - 1; i <= j;) { // Note that here i <= j, because we need to handle two elements at the end
            if (A[i] * A[i] < A[j] * A[j])  {
                result[k--] = A[j] * A[j];
                j--;
            }
            else {
                result[k--] = A[i] * A[i];
                i++;
            }
        }
        return result;
    }
};

class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
        int result = INT32_MAX;
        int sum = 0; // Sum of the sliding window values
        int i = 0; // Starting position of the sliding window
        int subLength = 0; // Length of the sliding window
        for (int j = 0; j < nums.size(); j++) {
            sum += nums[j];
            // Note that here we use while, updating i (starting position) each time and continuously comparing whether the subsequence meets the condition
            while (sum >= s) {
                subLength = (j - i + 1); // Get the length of the subsequence
                result = result < subLength ? result : subLength;
                sum -= nums[i++]; // This reflects the essence of the sliding window, constantly changing i (the starting position of the subsequence)
            }
        }
        // If result has not been assigned, return 0, indicating no subsequence meets the condition
        return result == INT32_MAX ? 0 : result;
    }
};

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> res(n, vector<int>(n, 0)); // Use vector to define a two-dimensional array
        int startx = 0, starty = 0; // Define the starting position for each loop
        int loop = n / 2; // How many times each loop runs, for example, if n is odd 3, then loop = 1, just loop once, the middle value of the matrix needs to be handled separately
        int mid = n / 2; // The middle position of the matrix, for example: if n is 3, the middle position is (1,1), if n is 5, the middle position is (2, 2)
        int count = 1; // Used to assign values to each space in the matrix
        int offset = 1; // Needs to control the length of each edge traversed in each loop, shrinking the right boundary by one each time
        int i,j;
        while (loop --) {
            i = startx;
            j = starty;

            // The following four for loops simulate a complete loop
            // Simulate filling the upper row from left to right (closed left and open right)
            for (j; j < n - offset; j++) {
                res[i][j] = count++;
            }
            // Simulate filling the right column from top to bottom (closed left and open right)
            for (i; i < n - offset; i++) {
                res[i][j] = count++;
            }
            // Simulate filling the lower row from right to left (closed left and open right)
            for (; j > starty; j--) {
                res[i][j] = count++;
            }
            // Simulate filling the left column from bottom to top (closed left and open right)
            for (; i > startx; i--) {
                res[i][j] = count++;
            }

            // When starting the second loop, the starting positions need to be incremented by 1, for example: the starting position of the first loop is (0, 0), the starting position of the second loop is (1, 1)
            startx++;
            starty++;

            // Offset controls the length of each edge traversed in each loop
            offset += 1;
        }

        // If n is odd, need to assign a value to the middle position of the matrix separately
        if (n % 2) {
            res[mid][mid] = count;
        }
        return res;
    }
};