'2025/03/18'에 해당되는 글 1건

Leetcode Problem:

• Longest Nice Subarray

Summary

• The problem is to find the length of the longest nice subarray in a given array of positive integers.

Approach

• The approach used is to use a sliding window technique, where we keep expanding the window to the right as long as the bitwise AND of the current prefix sum and the next element is 0
• If the condition is not met, we shrink the window from the left.

Complexity

• O(n), where n is the number of elements in the array.

Explanation

• The solution code initializes two pointers, l and r, to the start of the array
• It also initializes a variable, prefixSum, to keep track of the bitwise AND of the current prefix sum and the next element
• The code then enters a loop where it checks if the bitwise AND of the current prefix sum and the next element is 0
• If it is, the code adds the next element to the prefix sum and moves the right pointer to the right
• If it is not, the code subtracts the leftmost element from the prefix sum and moves the left pointer to the right
• The code keeps track of the maximum length of the nice subarray and returns it at the end.

Solution Code:

class Solution {
public:
    int longestNiceSubarray(vector& nums) {
        int l = 0;
        int r = 0;
        int prefixSum = 0;
        int ans = 0;
        while(l < nums.size() && r < nums.size()){
            if((prefixSum & nums[r]) == 0){
                prefixSum += nums[r];
                r++;
                ans = max(ans, r - l);
            }else{
                prefixSum -= nums[l];
                l++;
            }
        }
        return ans;
    }
};