class Solution { public int numberOfArithmeticSlices(int[] nums) { /* Q57 of dp playlist , every cell denotes total no. of subarrays APs of size >=2 ending at that ith element. here dp is an array of HM we make a HM[] to store common difference -> no.of Ap for all elements */ int n = nums.length , ans = 0; //making HM HashMap<Integer,Integer>[] map = new HashMap[n]; //iniitalizing all hashmap in hashmap[] for(int i = 0 ; i < n ; i++) map[i] = new HashMap<>(); //common approach of LIS for(int i = 1 ; i < n ;i++){ for(int j = i-1 ; j >= 0 ; j--){ long cd = (long)nums[i]-(long)nums[j]; //edge case if cd goes out of integer range if(cd <= Integer.MIN_VALUE || cd >= Integer.MAX_VALUE)continue; /*we traverse the array in LIS fashion to store subarray ap of size >=2 for each element if at any moment we find that the common difference found by nums[i] - nums[j] already exists that means current element is going to be the 3rd or more member of the AP so now total no. of AP's of length >=3 increases by 1 and we add to the answer */ if(map[j].containsKey((int)cd)){ int AP = map[j].get((int)cd); map[i].put((int)cd , map[i].getOrDefault((int)cd,0) + AP+1); ans += AP; } /* if its a new (cd then we just add it to the map and they become a 2 sized ap , if in the future some number has same common difference it will add to this AP */ else map[i].put((int)cd , map[i].getOrDefault((int)cd,0)+1); } } return ans; } }
Preview:
downloadDownload PNG
downloadDownload JPEG
downloadDownload SVG
Tip: You can change the style, width & colours of the snippet with the inspect tool before clicking Download!
Click to optimize width for Twitter