# 220. Contains Duplicate III

題目：<https://leetcode.com/problems/contains-duplicate-iii/>

解法：使用 sliding window 加上 binary search tree 來解，依照題目 indexDiff 的限制，以 sliding window 的概念，依序搜尋第 i - indexDiff 到第 i - 1 個元素是否符合 valueDiff 條件，為了加速搜尋使用 AVL tree 來搜尋，若找不到符合條件的元素，則刪除 AVL tree 中第 i - indexDiff 個元素，加入第 i 個元素，在接續往下搜尋。

Python3：

class AVLNode(object):
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
        self.height = 1

class AVLTree(object):
    def insertNode(self, node, val):
        if not node:
            return AVLNode(val)
        if val < node.val:
            node.left = self.insertNode(node.left, val)
        else:
            node.right = self.insertNode(node.right, val)
        return self.balance(node)

    def deleteNode(self, node, val):
        if node is None:
            return node
        if val < node.val:
            node.left = self.deleteNode(node.left, val)
        elif val > node.val:
            node.right = self.deleteNode(node.right, val)
        else:
            if node.left is None:
                return node.right
            elif node.right is None:
                return node.left
            else:
                cur = node.right
                while cur.left:
                    cur = cur.left;
                node.val = cur.val
                node.right = self.deleteNode(node.right, cur.val)
        return self.balance(node)

    def balance(self, node):
        node.height = 1 + max(self.getHeight(node.left), self.getHeight(node.right))
        balanceFactor = self.getHeight(node.left) - self.getHeight(node.right)
        if balanceFactor > 1:
            if self.getHeight(node.left.left) > self.getHeight(node.left.right):
                return self.rightRotate(node)
            else:
                node.left = self.leftRotate(node.left)
                return self.rightRotate(node)
        if balanceFactor < -1:
            if self.getHeight(node.right.right) > self.getHeight(node.right.left):
                return self.leftRotate(node)
            else:
                node.right = self.rightRotate(node.right)
                return self.leftRotate(node)
        return node

    def leftRotate(self, node):
        top = node.right
        node.right = top.left
        top.left = node
        node.height = 1 + max(self.getHeight(node.left), self.getHeight(node.right))
        top.height = 1 + max(self.getHeight(top.left), self.getHeight(top.right))
        return top

    def rightRotate(self, node):
        top = node.left
        node.left = top.right
        top.right = node
        node.height = 1 + max(self.getHeight(node.left), self.getHeight(node.right))
        top.height = 1 + max(self.getHeight(top.left), self.getHeight(top.right))
        return top

    def getHeight(self, node):
        if not node:
            return 0
        return node.height

class Solution:
    def containsNearbyAlmostDuplicate(self, nums: list[int], indexDiff: int, valueDiff: int) -> bool:
        root = None
        for i in range(len(nums)):
            cur = root
            while cur:
                if nums[i] < cur.val - valueDiff:
                    cur = cur.left
                elif nums[i] > cur.val + valueDiff:
                    cur = cur.right
                else:
                    return True
            root = AVLTree().insertNode(root, nums[i])
            if i >= indexDiff:
                root = AVLTree().deleteNode(root, nums[i-indexDiff])
        return False
    
if __name__ == '__main__':
    nums = [1,5,9,1,5,9]
    indexDiff = 2
    valueDiff = 3
    
    ans = Solution().containsNearbyAlmostDuplicate(nums, indexDiff, valueDiff)
    print(ans)

C：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

int max(int a, int b) {
    return (a > b) ? a : b;
}

typedef struct AVLNode {
    int val;
    struct AVLNode *left;
    struct AVLNode *right;
    int height;
} AVLNode;

int getHeight(AVLNode *node) {
    if (node == NULL)
        return 0;
    return node->height;
}

AVLNode* leftRotate(AVLNode *node) {
    AVLNode *top = node->right;
    node->right = top->left;
    top->left = node;
    node->height = 1 + max(getHeight(node->left), getHeight(node->right));
    top->height = 1 + max(getHeight(top->left), getHeight(top->right));
    return top;
}

AVLNode* rightRotate(AVLNode *node) {
    AVLNode *top = node->left;
    node->left = top->right;
    top->right = node;
    node->height = 1 + max(getHeight(node->left), getHeight(node->right));
    top->height = 1 + max(getHeight(top->left), getHeight(top->right));
    return top;
}

AVLNode* balance(AVLNode *node) {
    node->height = 1 + max(getHeight(node->left), getHeight(node->right));
    int balanceFactor = getHeight(node->left) - getHeight(node->right);
    if (balanceFactor > 1) {
        if (getHeight(node->left->left) > getHeight(node->left->right)) {
            return rightRotate(node);
        } else {
            node->left = leftRotate(node->left);
            return rightRotate(node);
        }
    }
    if (balanceFactor < -1) {
        if (getHeight(node->right->right) > getHeight(node->right->left)) {
            return leftRotate(node);
        } else {
            node->right = rightRotate(node->right);
            return leftRotate(node);
        }
    }
    return node;
}

AVLNode* insertNode(AVLNode *node, int val) {
    if (node == NULL) {
        node = (AVLNode*)malloc(sizeof(AVLNode));
        node->val = val;
        node->left = NULL;
        node->right = NULL;
        node->height = 1;
        return node;
    }
    if (val < node->val)
        node->left = insertNode(node->left, val);
    else if (val > node->val)
        node->right = insertNode(node->right, val);
    return balance(node);
}

AVLNode* deleteNode(AVLNode *node, int val) {
    if (node == NULL)
        return node;
    if (val < node->val)
        node->left = deleteNode(node->left, val);
    else if (val > node->val)
        node->right = deleteNode(node->right, val);
    else {
        if (node->left == NULL) {
            AVLNode *cur = node->right;
            free(node);
            return cur;
        } else if (node->right == NULL) {
            AVLNode *cur = node->left;
            free(node);
            return cur;
        } else {
            AVLNode *cur = node->right;
            while (cur->left != NULL)
                cur = cur->left;
            node->val = cur->val;
            node->right = deleteNode(node->right, cur->val);
        }
    }
    return balance(node);
}

// Print the tree
void printPreOrder(AVLNode *root) {
  if (root != NULL) {
    printf("%d ", root->val);
    printPreOrder(root->left);
    printPreOrder(root->right);
  }
}

bool containsNearbyAlmostDuplicate(int* nums, int numsSize, int indexDiff, int valueDiff) {
    AVLNode *root = NULL;
    for (int i = 0; i < numsSize; i++) {
        AVLNode *cur = root;
        while (cur != NULL) {
            if (nums[i] < cur->val - valueDiff)
                cur = cur->left;
            else if (nums[i] > cur->val + valueDiff)
                cur = cur->right;
            else
                return true;
        }
        root = insertNode(root, nums[i]);
        if (i >= indexDiff)
            root = deleteNode(root, nums[i-indexDiff]);
    }
    return false;
}

int main()
{
    int nums[] = {1,5,9,1,5,9};
    int numsSize = sizeof(nums) / sizeof(nums[0]);
    int indexDiff = 2, valueDiff = 3;
    
    bool ans = containsNearbyAlmostDuplicate(nums, numsSize, indexDiff, valueDiff);
    printf("%s\n", ans ? "True" : "False");
    return 0;
}

###### tags: `leetcode` `binary tree` `binary search tree` `AVL tree` `sliding window`