930. Binary Subarrays With Sum

class Solution {
    public int numSubarraysWithSum(int[] A, int S) {
        int left = 0, right = 0, idx = 0;
        int sumL = 0, sumR = 0;
        int cnt = 0;
        while (idx < A.length) {
            sumL += A[idx];
            while (left  S) {
                sumL -= A[left++];
            }
            sumR += A[idx];
            while (right  S || A[right] == 0)) {
                sumR -= A[right++];
            }
            if (sumR == S) // or sumL == S
                cnt += right - left + 1;
            idx++;
        }
        return cnt;
    }
}

For example
S = 2
1 0 0 1 0 1
x left x right x idx

567. Permutation in String

2N

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        int len1 = s1.length(), len2 = s2.length();
        if (len1 > len2) return false;
        int[] perm = new int[256];
        for (char c : s1.toCharArray()) {
            perm[c]++;
        }
        int[] cur = Arrays.copyOf(perm, 256);
        int i = 0, j = 0;
        while (j < len2) {
            char c = s2.charAt(j);
            if (perm[c] == 0) {
                i = j+1;
                cur = Arrays.copyOf(perm, 256);//!!
            }
            else if (cur[c] == 0) {
                while (i < j && cur[c] == 0) {
                    cur[s2.charAt(i)]++;
                    i++;
                }
                cur[c]--;//!!
            } else {
                cur[c]--;    
            }
            
            j++;
            if (j-i == len1) return true;
        }
        return j-i == len1;
    }
}

643. Maximum Average Subarray I

Need to write clean code quickly.
!!Nums can be negative.

    public double findMaxAverage(int[] nums, int k) {
        int i = 0, j = i, sum = 0;
        while (j < k) {
            sum += nums[j++];
        }
        int max = sum;
        while (j < nums.length) {
            sum += nums[j++];
            sum -= nums[i++];

            if (sum > max) {
                max = sum;   
            }
        }
        return (double)max/k;
    }

567. Permutation in String

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        if (s1.isEmpty() || s1.equals(s2)) return true;
        else if (s2.length() < s1.length()) return false;
        
        int[] set = new int[256];
        for (char c : s1.toCharArray()) set[c]++;
        int i = 0, j = 0;
        char[] src = s2.toCharArray();
        while (j < src.length) {
            char c = src[j];
            if (set[c] > 0) {
                set[c]--;
                j++;
                if (j-i == s1.length()) return true;
            } else {
                while (i < j && src[i] != c) {
                    set[src[i++]]++;
                }
                if (i < src.length && src[i] == c) {
                    i++;
                    j++;
                }
            }
        }
        return false;
    }
}

Find the Duplicate Number

    def findDuplicate(self, nums):
        size = len(nums)
        i, j = 1, 1+size
        while i <= j:
            mid = (i+j)//2
            x = y = 0
            for num in nums:
                if num < mid:
                    x += 1
                elif num == mid:
                    y += 1
                    if y > 1:
                        return mid
            if x > mid - 1:
                j = mid - 1
            else:
                i = mid + 1

Sliding Window Maximum

    def maxSlidingWindow(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """
        res = []
        deq = deque([])
        i = j = 0
        size = len(nums)
        while j < size:
            num = nums[j]
            # Delete extra element
            if j >= k:
                if nums[i] == deq[-1]:
                    deq.remove(nums[i])
                i += 1
            # Add element to deq if necessary
            while deq and deq[0] < num:
                deq.popleft()
            deq.appendleft(num)
            # Add max to result list
            if j >= k - 1:
                res.append(deq[-1])
            j += 1
        return res

Movezeros

j遇到0就前进，否则swap，所以把0换到了后面。

    def moveZeroes(self, nums):
        """
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        size = len(nums)
        i = 0
        for j in range(size):
            if nums[j] != 0:
                nums[i], nums[j] = nums[j], nums[i]
                i += 1

Contains Duplicate II

    def containsNearbyDuplicate(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: bool
        """
        if k == 0: return False
        exist = set()
        size = len(nums)
        i, j = 0, 0
        while j < size:
            if nums[j] in exist:
                return True
            if j - i == k:
                exist.remove(nums[i])
                i += 1
            exist.add(nums[j])
            j += 1
        return False

Minimum Size Subarray Sum

两个指针从左边移动的活动窗口可以遍历所有情况，切记！

O(n)

    def minSubArrayLen(self, s, nums):
        if len(nums) == 0: return 0
        i = 0
        j = 0
        all = 0
        res = len(nums) + 1
        while j < len(nums):
            all += nums[j]
            while all >= s and i <= j:
                if i == j: return 1
                res = min(res, j-i+1)
                all -= nums[i]
                i += 1
            j += 1
        return res if res < len(nums) + 1 else 0

O(nlogn)
http://www.jyuan92.com/blog/leetcode-minimum-size-subarray-sum/

Codility: CountTriangle

第一层loop设置initial index
Tricky:
// index will always be greater than j. If j becomes equal to index, then
// above loop will increment index, because arr[index] + arr[i] is always
// greater than arr[index]

    public int solution(int[] A) {
        Arrays.sort(A);
        int count = 0;
        int len = A.length;
        
        for (int i = 0; i+2 < len; i++) {
            int index = i+2;
            for (int j = i+1; j+1 < len; j++) {
                while (index < len && A[i]+A[j] > A[index]) {
                    index++;
                }
                count += index-j-1;
            }
        }
        return count;
    }