NC54数组中相加和为0的三元组

• 排序
• 依次遍历
  • 当前数 > 0 跳过
  • 当前的数与前一个相等 跳过
  • 俩个指针 i 从 当前的下一个开始 j从最后一个开始，若当前的和大于0，j–；若当前的和小于0，i++。若等于零，则得到一种解，i++，j–，要注意i，j在移动时也需要注意去重。

javascript">/**
 * 
 * @param num int整型一维数组 
 * @return int整型二维数组
 */
function threeSum( num ) {
    if(!num || num.length < 3) return [];
    let ans = [];
    num.sort((a , b) => a > b ? 1 : -1);
    for(let now = 0 ; now < num.length - 2 ; now ++ ){
        if(num[now] > 0) continue;
        if(now != 0 && num[now] == num[now - 1] ) continue;
        let i = now + 1;
        let j = num.length - 1;
        while(i < j){
            if(num[i] + num[j] + num[now] == 0){
                let each = [ num[now] , num[i] , num[j]];
                ans.push(each)
                i++;
                while(num[i] == num[i - 1]){
                    i++;
                }
                j--;
                while(num[j] == num[j + 1]){
                    j--;
                }
            }else if(num[i] + num[j] + num[now] > 0){
                j--;
                while(num[j] == num[j + 1]){
                    j--;
                }
            }else if(num[i] + num[j] + num[now] < 0){
                i++;
                while(num[i] == num[i - 1]){
                    i++;
                }
            }
        }
    }
    return ans;
}
module.exports = {
    threeSum : threeSum
};

NC66在二叉树中找到俩个节点的最近公共祖先

深度先序遍历二叉树，如果当前节点，左子树，右子树中三者俩个是p，q则当前节点是公共祖先，找到的第一个就是，直接存起来即可。

javascript">/*
 * function TreeNode(x) {
 *   this.val = x;
 *   this.left = null;
 *   this.right = null;
 * }
 */

/**
 * 
 * @param root TreeNode类 
 * @param o1 int整型 
 * @param o2 int整型 
 * @return int整型
 */
let ans = -1;
function lowestCommonAncestor( root ,  o1 ,  o2 ) {
    function dfs(root){
        if(root == null){
            return false;
        }
        let l = dfs(root.left);
        let r = dfs(root.right);
        let m = root.val == o1 || root.val == o2;
        if((l && r) || (l && m) || (r && m)){
            if(ans == -1) ans = root.val;
        }
        return l || r || m;
    }
    dfs(root);
    return ans;
}

module.exports = {
    lowestCommonAncestor : lowestCommonAncestor
};