C# O(n^2)


  • 0

    Any more improvements here are to do with coding quirks. Leetcode's C# Timelimits are too tight.

    public class Solution {
        public int NumberOfArithmeticSlices(int[] A) {
            int counts = 0;
            if (A.Length == 0)
            {
                return counts;    
            }
            
            Dictionary<int, int>[] dp = new Dictionary<int, int>[A.Length];
            dp[0] = new Dictionary<int, int>();
            for(int i = 1; i < A.Length; i++)
            {
                dp[i] = new Dictionary<int, int>();
                for(int j = i-1; j >= 0; j--)
                {
                    long diff = (long)A[i] - (long)A[j];
                    if (diff <= Int32.MinValue || diff > Int32.MaxValue) continue;
                    int df = (int)diff;
                    if (!dp[i].ContainsKey(df))
                    {
                        dp[i][df] = 0; 
                    }
                    
                    dp[i][df]++;
                    
                    // Get j's dictionary for the given diff.
                    if (dp[j].ContainsKey(df))
                    {
                       var jsDiffCounts = dp[j][df];
                       dp[i][df] += jsDiffCounts;
                       counts += dp[j][df];
                    }
                }
            }
            
            return counts;
            
        }
    }
    

  • 0

    why you skip i=0 loop?

    My code is similar

        public int NumberOfArithmeticSlices2(int[] A)
        {
            int res = 0;
            Dictionary<int, int>[] map = new Dictionary<int, int>[A.Length];
    
            for (int i = 0; i < A.Length; i++)
            {
                map[i] = new Dictionary<int, int>();
    
                for (int j = 0; j < i; j++)
                {
                    long diff = (long) A[i] - (long) A[j];
                    if (diff < int.MinValue || diff > int.MaxValue) continue;
    
                    int d = (int) diff;
    
                    int jDiff = map[j].ContainsKey(d) ? map[j][d] : 0;
                    int increase = jDiff + 1; //the amout of increase for each time
    
                    /* The sub min is 3, res += increase > 1 ? (increase -1 ) : 0
                     * If min is 4, res += increase > 2 ? (increase -2) : 0
                     */
    
                    res += increase > 1 ? (increase - 1) : 0;
    
                    if (!map[i].ContainsKey(d))
                        map[i].Add(d, increase);
                    else
                        map[i][d] += increase; 
                }
                
            }
            return res;
        }
    

  • 0

    @new2500 -If i = 0, the inner loop will not execute anyway. I have initialized dp[0] outside the loop. So, it does not make a difference.


Log in to reply
 

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