Java solution beats 98.18%


  • 1
    public class Solution {
        public int numberOfArithmeticSlices(int[] A) {
            int res = 0;
            
            Map<Integer, List<Integer>> m = new HashMap<>();
            for (int i = 0; i < A.length; i++) {
                m.putIfAbsent(A[i], new ArrayList<>());
                m.get(A[i]).add(i);
            }
            for (Map.Entry<Integer, List<Integer>> e : m.entrySet()) {
                if (e.getValue().size() > 2) {
                    int n = e.getValue().size();
                    res += (1 << n) - 1 - n - n * (n - 1) / 2;
                }
            }
            
            for (int i = 0; i < A.length; i++) {
                for (int j = i + 1; j < A.length; j++) {
                    if (A[j] == A[i] || (long) A[j] - A[i] > Integer.MAX_VALUE || (long) A[j] - A[i] < Integer.MIN_VALUE) {
                        continue; 
                    }
                    
                    res += helper(A, A[j], A[j] - A[i], j, m);
                }
            }
            
            return res;
        }
        
        private int helper(int[] A, int curr, int d, int idx, Map<Integer, List<Integer>> m) {
            if ((long) curr + d > Integer.MAX_VALUE || (long) curr + d < Integer.MIN_VALUE || !m.containsKey(curr + d)) {
                return 0;
            }
            
            int res = 0;
            curr += d;
            List<Integer> list = m.get(curr);
            for (int i : list) {
                if (i > idx) {
                    res += helper(A, curr, d, i, m) + 1;
                }
            }
            return res;
        }
    }
    

  • 0
    S

    @lufangjianle
    Can you share some thoughts behind the code? Especially, how can you derive the equations in the code?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.