<?php

function getMsectime() {
    list($msec, $sec) = explode(' ', microtime());
    return (float)sprintf('%.0f', (floatval($msec) + floatval($sec)) * 1000);
}
echo "<pre>";
class Solution {
    /**
     * @param String $s
     * @param String $t
     * @return Boolean
     */
    function isAnagram1($s, $t) {
        $sLen = floor(strlen($s)/2);
        $sArr = $tArr = [];
        for ($i = 0; $i < $sLen; $i++) { 
            $sArr[$s[$i]]++;
            $tArr[$s[$i]] = 0;
            if (strlen($s)%2 == 1) {                
                $sArr[$s[2*$sLen-$i]]++;
                $tArr[$s[2*$sLen-$i]] = 0;
            } else {
                $sArr[$s[2*$sLen-$i-1]]++;
                $tArr[$s[2*$sLen-$i-1]] = 0;
            }
        }
        if (strlen($s)%2 == 1) {
            $sArr[$s[$sLen]]++;
        }

        $tLen = floor(strlen($t)/2);
        for ($i = 0; $i < $tLen; $i++) { 
            $tArr[$t[$i]]++;            
            if (strlen($s)%2 == 1) {                
                $tArr[$t[2*$tLen-$i]]++;
            } else {
                $tArr[$t[2*$tLen-$i-1]]++;
            }
        }
        if (strlen($t)%2 == 1) {
            $tArr[$t[$tLen]]++;
        }

        return $sArr == $tArr;
    }

    /**
     * @param String $s
     * @param String $t
     * @return Boolean
     */
    function isAnagram($s, $t) {
        if (strlen($s) !== strlen($t)) {
            return false;
        };

        $len = floor(strlen($s)/2);
        $table = [];
        for ($i = 0; $i < $len; $i++) { 
            $table[$s[$i]]++;
            if (strlen($s)%2 == 1) {                
                $table[$s[2*$len-$i]]++;
            } else {
                $table[$s[2*$len-$i-1]]++;
            }

            
            if (!isset($table[$t[$i]])) {
                $table[$t[$i]] = 0;
            }
            $table[$t[$i]]--;
            if (strlen($t)%2 == 1) {
                if (!isset($table[$t[2*$len-$i]])) {
                    $table[$t[2*$len-$i]] = 0;
                }
                $table[$t[2*$len-$i]]--;
            } else {
                if (!isset($table[$t[2*$len-$i-1]])) {
                    $table[$t[2*$len-$i-1]] = 0;
                }
                $table[$t[2*$len-$i-1]]--;
            }
        }
        if (strlen($s)%2 == 1) {
            $table[$s[$len]]++;
            $table[$t[$len]]--;
        }

        foreach ($table as $key => $value) {
            if ($value !== 0) {
                return false;
            }
        }

        return true;
    }

    /**
     * 
     * 349. 两个数组的交集
     * 给定两个数组，编写一个函数来计算它们的交集。
     * 
     * @param Integer[] $nums1
     * @param Integer[] $nums2
     * @return Integer[]
     */
    function intersection($nums1, $nums2) {
        $res = [];
        $table = [];
        for ($i=0; $i < count($nums1); $i++) { 
            $table[$nums1[$i]] = 1;
        }

        for ($i=0; $i < count($nums2); $i++) { 
            if (isset($table[$nums2[$i]])) {
                $res[] = $nums2[$i];
            } else {
                unset($table[$nums2[$i]]);
            }
        }

        return $res;
    }



    /**
     * 
     * 349. 两个数组的交集
     * 给定两个数组，编写一个函数来计算它们的交集。
     * 
     * @param Integer[] $nums1
     * @param Integer[] $nums2
     * @return Integer[]
     */
    function intersect($nums1, $nums2) {
        $res = [];
        $table = [];
        for ($i=0; $i < count($nums1); $i++) { 
            $table[$nums1[$i]]++;
        }

        for ($i=0; $i < count($nums2); $i++) { 
            if (isset($table[$nums2[$i]]) && $table[$nums2[$i]] > 0) {
                $res[] = $nums2[$i];
                $table[$nums2[$i]]--;
            }
        }

        return $res;
    }

    /**
     * 202. 快乐数
     * 
     * 编写一个算法来判断一个数 n 是不是快乐数。
     * 「快乐数」定义为：
     * 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
     * 然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
     * 如果 可以变为1，那么这个数就是快乐数。
     * 如果 n 是快乐数就返回 true ；不是，则返回 false 。
     * 
     * 输入：19
     * 输出：true
     * 解释：
     * 1^2 + 9^2 = 82
     * 8^2 + 2^2 = 68
     * 6^2 + 8^2 = 100
     * 1^2 + 0^2 + 0^2 = 1
     * 
     * @param Integer $n
     * @return Boolean
     */
    function isHappy($n) {
        $map = [];
        while (!isset($map[$n]) && $map[$n] !== 1) {
            $t = 0;
            $n = (string)$n;
            for ($i=0; $i < strlen($n); $i++) { 
                $t += $n[$i]*$n[$i];
            }
            $map[$n] = $t;
            $n = $t;
        }

        return $n === 1;
    }

    /**
     * 第454题.四数相加II
     * 
     * 给你四个整数数组 nums1、nums2、nums3 和 nums4 ，数组长度都是 n ，请你计算有多少个元组 (i, j, k, l) 能满足：
     *   0 <= i, j, k, l < n
     *   nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0
     * 
     * 输入：nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2]
     * 输出：2
     * 
     * 解释：
     * 两个元组如下：
     * 1. (0, 0, 0, 1) -> nums1[0] + nums2[0] + nums3[0] + nums4[1] = 1 + (-2) + (-1) + 2 = 0
     * 2. (1, 1, 0, 0) -> nums1[1] + nums2[1] + nums3[0] + nums4[0] = 2 + (-1) + (-1) + 0 = 0
     * 
     * @param Integer[] $nums1
     * @param Integer[] $nums2
     * @param Integer[] $nums3
     * @param Integer[] $nums4
     * @return Integer
     */
    function fourSumCount($nums1, $nums2, $nums3, $nums4) {
        foreach ($nums1 as $n1) {
            foreach ($nums2 as $n2) {
                $map[$n1 + $n2] += 1;
            }
        }
        $count = 0;
        foreach ($nums3 as $n3) {
            foreach ($nums4 as $n4) {
                $sum = $n3 + $n4;
                if (isset($map[-$sum])) {
                    $count += $map[-$sum];
                }
            }
        }
        return $count;
    }

    /**
     * 
     * 383. 赎金信
     * 
     * 为了不在赎金信中暴露字迹，从杂志上搜索各个需要的字母，组成单词来表达意思。
     * 给你一个赎金信 (ransomNote) 字符串和一个杂志(magazine)字符串，判断 ransomNote 能不能由 magazines 里面的字符构成。
     * 如果可以构成，返回 true ；否则返回 false 。
     * magazine 中的每个字符只能在 ransomNote 中使用一次。
     * 
     * @param String $ransomNote
     * @param String $magazine
     * @return Boolean
     */
    function canConstruct($ransomNote, $magazine) {
        $map = [];
        for ($i=0; $i < strlen($magazine); $i++) { 
            $map[$magazine[$i]]++;
        }
        for ($i=0; $i < strlen($ransomNote); $i++) { 
            if (!isset($map[$ransomNote[$i]])) {
                return false;
            }
            $map[$ransomNote[$i]]--;
            if ($map[$ransomNote[$i]] < 0) {
                return false;
            }
        }
        return true;
    }

    /**
     * 三数之和
     * 
     * 给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。
     * 注意： 答案中不可以包含重复的三元组。
     * 
     * 示例：
     *   给定数组 nums = [-1, 0, 1, 2, -1, -4]，
     *   满足要求的三元组集合为： [ [-1, 0, 1], [-1, -1, 2] ]
     * 
     * @param Integer[] $nums
     * @return Integer[][]
     */
    function threeSum($nums) {

    }
}

$solution = new Solution;
// $s = "anagram";
// $t = "nagaram";

// $s = "rat";
// $t = "car";

// $s = "ba";
// $t = "ab";

// var_dump($solution->isAnagram($s, $t));


// $nums1 = [1,2,2,1];
// $nums2 = [2, 2];
// var_dump($solution->intersection($nums1, $nums2));

// $nums1 = [4,9,5];
// $nums2 = [9,4,9,8,4];
// var_dump($solution->intersect($nums1, $nums2));

// $n = 19;
// var_dump($solution->isHappy($n));

// $nums1 = [1,2];
// $nums2 = [-2,-1];
// $nums3 = [-1,2];
// $nums4 = [0,2];
// var_dump($solution->fourSumCount($nums1, $nums2, $nums3, $nums4));

// $ransomNote = "a"; $magazine = "b";    // false
// $ransomNote = "aa"; $magazine = "ab";  // false
// $ransomNote = "aa"; $magazine = "aab"; // true
// var_dump($solution->canConstruct($ransomNote, $magazine));

$nums = [-1, 0, 1, 2, -1, -4];
var_dump($solution->threeSum($nums));