Given an integer array of sizen, find all elements that appear more than⌊ n/3 ⌋times. The algorithm should run in linear time and in O(1) space.

class Solution {
    public List<Integer> majorityElement(int[] nums) {
        List<Integer> ans = new ArrayList<>();
        if (nums == null || nums.length == 0) return ans;

        int candidate1 = Integer.MIN_VALUE, candidate2 = Integer.MIN_VALUE;
        int count1 = 0, count2 = 0;

        for (int num : nums){
            if (num == candidate1){
                count1++;
            }
            else if (num == candidate2){
                count2++;
            }
            else if (count1 == 0){
                candidate1 = num;
                count1 = 1;
            }
            else if (count2 == 0){
                candidate2 = num;
                count2 = 1;
            }
            else{
                count1--;
                count2--;
            }
        }

        count1 = 0;
        count2 = 0;
        for (int num : nums){
            if (num == candidate1) count1++;
            if (num == candidate2) count2++;
        }

        if (count1 > nums.length / 3 && !ans.contains(candidate1)) ans.add(candidate1);
        if (count2 > nums.length / 3 && !ans.contains(candidate2)) ans.add(candidate2);

        return ans;
    }
}