thảo luận Leetcode mỗi ngày

use std::collections::*;

impl Solution {
    pub fn min_subarray(nums: Vec<i32>, p: i32) -> i32 {
        let n = nums.len();

        let (mut seen_residues, mut lengths): (HashSet<i32>, HashMap<i32, usize>) =
            (HashSet::new(), HashMap::new());

        let mut new_pairs = vec![];

        for num in nums {
            let residue = num.rem_euclid(p);

            for seen_residue in seen_residues.iter().copied() {
                let seen_length = lengths[&seen_residue];
                let new_residue = (seen_residue + residue) % p;

                new_pairs.push((new_residue, seen_length + 1));
            }

            for (new_residue, new_length) in new_pairs.iter().copied() {
                seen_residues.insert(new_residue);

                lengths.entry(new_residue).
                    and_modify(|len| *len = (*len).max(new_length)).
                    or_insert(new_length);
            }

            new_pairs.clear();

            lengths.entry(residue).or_insert(1);
            seen_residues.insert(residue);
        }

        match lengths.get(&0) {
            Some(len) => (n - len) as i32,
            None => -1
        }
    }
}

use std::collections::HashMap;

impl Solution {
    pub fn min_subarray(nums: Vec<i32>, p: i32) -> i32 {
        let n = nums.len();

        let sum =
            nums.iter().copied().
                fold(0, |sum, num| (sum + num) % p);

        if sum == 0 {
            return 0;
        }

        let mut seen = HashMap::new();
        let (mut prefix, mut min_len) = (0, n);
        seen.insert(0, 0);

        for (i, num) in nums.into_iter().enumerate() {
            prefix = (prefix + num) % p;

            let diff = (prefix - sum).rem_euclid(p);

            if let Some(j) = seen.get(&diff) {
                min_len = min_len.min(i + 1 - j);
            }

            seen.insert(prefix, i + 1);
        }

        if min_len == n {
            return -1;
        }

        min_len as i32
    }
}

use std::collections::*;

impl Solution {
    pub fn divide_players(mut skill: Vec<i32>) -> i64 {
        skill.sort_unstable();
        let n = skill.len();

        let target = skill[0] + skill[n - 1];
        let mut result = 0;

        for i in (0..(n / 2)) {
            if skill[i] != target - skill[n - 1 - i] {
                return -1;
            }

            result += skill[i] as i64 * skill[n - 1 - i] as i64;
        }

        result
    }
}

public class Solution
{
    public long DividePlayers(int[] skill)
    {
        if (skill.Length == 2)
        {
            return skill[0] * skill[1];
        }
        Dictionary<int, int> map = new();
        int sum = 0;
        int teamCount = skill.Length / 2;
        for (int i = 0; i < skill.Length; i++)
        {
            int mem = skill[i];
            sum += mem;
            if (!map.ContainsKey(mem))
            {
                map.Add(mem, 0);
            }
            map[mem]++;
        }

        if (sum % teamCount != 0)
        {
            return -1;
        }
        int teamSkill = sum / teamCount;
        long result = 0;
        for (int i = 0; i < skill.Length; i++)
        {
            int mem1 = skill[i];
            if (map[mem1] == 0)
            {
                continue;
            }
            map[mem1]--;

            int mem2 = teamSkill - mem1;
            map.TryGetValue(mem2, out int mem2Count);
            if (mem2Count == 0)
            {
                return -1;
            }
            map[mem2]--;
            result += mem1 * mem2;
        }

        return result;
    }
}

class Solution {
    public long dividePlayers(int[] skill) {
        int n = skill.length;

        int sum = 0;
        for (int s : skill) {
            sum += s;
        }

        int target = 0;
        if (sum % (n / 2) != 0) {
            return -1;
        } else {
            target = sum / (n / 2);
        }

        Map<Integer, Integer> map = new HashMap<>();

        long res = 0l;
        int count = 0;
        
        for (int s : skill) {
            int need = target - s;
            if (map.containsKey(need) && map.get(need) > 0) {
                res += s * 1l * need * 1l;
                count++;
                map.put(need, map.get(need) - 1);
            } else {
                map.put(s, map.getOrDefault(s, 0) + 1);
            }
        }

        return count != (n / 2) ? -1 : res;
    }
}

class Solution {
    public long dividePlayers(int[] skill) {
        Arrays.sort(skill);

        int left = 0, right = skill.length - 1;
        int target = skill[left] + skill[right];

        long rs = 0;

        while(left < right) {
            if (skill[left] + skill[right] != target)
                return -1;

            rs += skill[left] * skill[right];
            left++;
            right--;
        }

        return rs;
    }
}

class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        count1 = [0]*26
        count2 = [0]*26
        def isEquals():
            for i in range(26):
                if count1[i] != count2[i]:
                    return False

            return True

        for char in s1:
            count1[ord(char) - ord('a')] += 1

        left = 0
        n = len(s1)
        for i, char in enumerate(s2):
            count2[ord(char) - ord('a')] += 1
            if isEquals():
                return True
        
            if i >= n - 1:
                count2[ord(s2[left]) - ord('a')] -= 1
                left += 1

        return False

var checkInclusion = function(s1, s2) {
    const m = s1.length, n = s2.length;
    if (m > n) {
        return false;
    }
    const g = Array(26).fill(0);
    for (const ch of s1) {
        g[ch.charCodeAt(0) - 97]++;
    }
    let j = 0;
    for (let i = 0; i < n; i++) {
        const charIdx = s2.charCodeAt(i) - 97;
        g[charIdx]--;
        while (g[charIdx] < 0) {
            g[s2.charCodeAt(j++) - 97]++;
        }
        if (i - j + 1 === m) {
            return true;
        }
    }
    return false;
};

class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        def isSameCounter(counter1, counter2):
            for c in counter1:
                if counter1[c] != counter2[c]:
                    return False
            return True
       
        m, n = len(s1), len(s2)
        if m > n:
            return False
       
        counter1, counter2 = defaultdict(int), defaultdict(int)
        for i, c in enumerate(s1):
            counter1[c] += 1
            counter2[s2[i]] += 1

        i = 0
        while i < n - m + 1:
            if isSameCounter(counter1, counter2):
                return True
            i += 1
            if i + m - 1 == n:
                break
            counter2[s2[i-1]] -= 1
            counter2[s2[m - 1 + i]] += 1
           
        return False

class Solution {
 
    public boolean checkInclusion(String s1, String s2) {
        int n = s2.length();
        int len =s1.length();
        int[] freq= new int[26];
        for(char c:s1.toCharArray()){
            freq[c-'a']++;
        }
        for(int i=0;i<26;i++){
            freq[i]= freq[i]==0?-2:freq[i];
        }
        int l =0;
        for(int r = 0 ; r<n;r++){
            char c =s2.charAt(r);
            if(freq[c-'a']==-2){
                while(l<=r){
                    char cc =s2.charAt(l);
                    if(freq[cc-'a']!=-2){
                       freq[cc-'a']++;
                    }
                    l++;
                }
            }
            else if(--freq[c-'a']<0) {
                while(freq[c-'a']<0){
                    freq[s2.charAt(l)-'a']++;
                    l++;
                }
               
            }
            //System.out.println(l);
            if(r-l+1==len) return true;
        }
        return false;
    }
}