/**
 * @param {number[]} nums
 * @return {boolean}
 */
var containsDuplicate = function(nums) {

    set = new Set();
    for(let num of nums){
        if(set.has(num)) return true;
        set.add(num);
    }
    return false;
};

/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
var isAnagram = function(s, t) {

    if(s.length != t.length) return false;

    // a -> charCode 97, z -> charCode 122 アルファベットは26文字
    const ary = new Array(26).fill(0);

    const start = 'a'.charCodeAt();
    for(let i=0; i<s.length; i++){
        ary[s.charCodeAt(i) - start]++;
        ary[t.charCodeAt(i) - start]--;
    }

    return !ary.some((item) => item !== 0);
};

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {

    const map = new Map();
    for(let i=0; i<nums.length; i++){
        const value = target - nums[i];
        if(map.has(value)) return [i, map.get(value)];
        map.set(nums[i], i);
    }
};

/**
 * @param {string[]} strs
 * @return {string[][]}
 */
var groupAnagrams = function(strs) {

    const map = {};
    for(let str of strs){
        const key = str.split('').sort().join('');

        if(key in map){
            map[key].push(str);
        }else{
            map[key] = [str];
        }
    }
    return Object.values(map);
}

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var topKFrequent = function(nums, k) {

    const map = {};
    for(let num of nums){
        if(num in map){
            map[num].count++;
        }else{
            map[num] = {key: num, count:1};
        }
    }
    return Object.values(map).sort((a, b)=>a.count - b.count).reverse().slice(0,k).map(item => item.key);
};

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var productExceptSelf = function(nums) {

    const n = nums.length;
    const result = new Array(n).fill(1);
    let start = 1;
    let end = 1;
    for(let i=0; i<n; i++){
        result[i] *= start;
        result[n-i-1] *= end;

        start *= nums[i];
        end *= nums[n-i-1];       
    }
    return result;
};

/**
 * @param {character[][]} board
 * @return {boolean}
 */
var isValidSudoku = function(board) {
    
    const n = board.length;
    const board2 = new Array(n).fill().map(_ => new Set());
    const trout = new Array(n).fill().map(_ => new Set());
    const column = new Array(n).fill().map(_ => new Set());
    for(let i=0; i<n; i++){

        for(let j=0; j<n; j++){
            const current = board[i][j];
            if(current === '.') continue;

            const index = 3 * Math.trunc(i/3) + Math.trunc(j/3);
            if(board2[i].has(current) || column[j].has(current) || trout[index].has(current)) {
                return false;
            }
            board2[i].add(current);
            column[j].add(current);
            trout[index].add(current);
        }
    }
    return true;
};

/**
 * @param {number[]} nums
 * @return {number}
 */
var longestConsecutive = function(nums) {

    let max = 0;
    const nums2 = new Set(nums);
    for(const current of nums2.values()){
        if(nums2.has(current - 1)) continue;

        let i=1;
        while(nums2.has(current + i)){
            i++;
        }
        max = Math.max(max, i);
    }

    return max;
};

/**
 * @param {string} s
 * @return {boolean}
 */
var isPalindrome = function(s) {
  
    let start = 0;
    let end = s.length - 1;
    while(start < end){
        while(start < end && /[^a-zA-Z0-9]/.test(s[start])) start++;
        while(start < end && /[^a-zA-Z0-9]/.test(s[end])) end--;

        if(s[start].toLowerCase() !== s[end].toLowerCase()) return false;
        start++;
        end--;
    }
    return true;
};

/**
 * @param {number[]} numbers
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(numbers, target) {

    let start = 0;
    let end = numbers.length - 1;
    while(start < end){
        const sum = numbers[start] + numbers[end];

        if(target === sum){
            return [start+1, end+1];
        }else if(target < sum){
            end--;
        }else{ // target > sum
            start++;
        }
    }
};